Sachverhalt:
Sachverhalt:
A. X._ wurde mit Urteil der Strafgerichtspräsidentin des Kantons Basel-Stadt vom 14. Februar 2003 vom Vorwurf der groben Verkehrsregelverletzung freigesprochen. Die Strafgerichtspräsidentin auferlegte X._ jedoch die Verfahrenskosten, da sie der Meinung war, er habe das Strafverfahren mutwillig wesentlich erschwert (vgl. <ref-law>/BS). Dieser Entscheid wurde ihm mit dem Hinweis auf das Appellationsrecht eröffnet.
X._ erklärte am 21. Februar 2003 die Appellation. Das Appellationsgericht des Kantons Basel-Stadt setzte ihm mit Verfügung vom 26. August 2003 Frist zur Begründung der Appellation an. Gleichzeitig ersucht es ihn, auch zur Frage Stellung zu nehmen, weshalb er meine, die Appellation ergreifen zu können. Das Appellationsgericht war der Ansicht, die Voraussetzung der Durchführung eines ordentlichen Verfahrens (vgl. <ref-law>/BS) erscheine fraglich, weil ein Verzeigungsverfahren durchgeführt worden sei. X._ reichte innert erstreckter Frist am 22. Oktober 2003 die Appellationsbegründung ein.
Das Appellationsgericht des Kantons Basel-Stadt, Ausschuss, trat am 5. Dezember 2003 auf die Appellation nicht ein. Es erwog, gegen den Entscheid der Strafgerichtspräsidentin wäre die Beschwerde nach §§ 184 ff. StPO/BS zu ergreifen gewesen. Beschwerden müssten aber nicht nur innert 10 Tagen angemeldet, sondern auch begründet werden. Die am 24. Februar 2003 eingegangene Appellationserklärung sei mit keinem Wort begründet worden. Sie könne daher nicht in eine gültige Beschwerde umgedeutet werden.
Das Appellationsgericht des Kantons Basel-Stadt, Ausschuss, trat am 5. Dezember 2003 auf die Appellation nicht ein. Es erwog, gegen den Entscheid der Strafgerichtspräsidentin wäre die Beschwerde nach §§ 184 ff. StPO/BS zu ergreifen gewesen. Beschwerden müssten aber nicht nur innert 10 Tagen angemeldet, sondern auch begründet werden. Die am 24. Februar 2003 eingegangene Appellationserklärung sei mit keinem Wort begründet worden. Sie könne daher nicht in eine gültige Beschwerde umgedeutet werden.
B. X._ führt mit Eingabe vom 23. März 2004 staatsrechtliche Beschwerde wegen Verletzung von <ref-law> (Grundsatz von Treu und Glauben) und <ref-law> (Vertrauensgrundsatz). Er beantragt die Aufhebung des Entscheides des Appellationsgerichts und dessen Rückweisung zur materiellen Beurteilung.
Die Strafgerichtspräsidentin verzichtet auf eine Vernehmlassung. Das Appellationsgericht spricht sich für Abweisung der Beschwerde aus.

Das Bundesgericht zieht in Erwägung:
Das Bundesgericht zieht in Erwägung:
1. Der Beschwerdeführer ist als Partei des kantonalen Verfahrens ohne weiteres legitimiert, mit staatsrechtlicher Beschwerde geltend zu machen, das Appellationsgericht sei zu Unrecht auf seine Appellation nicht eingetreten (<ref-ruling> E. 1.4; <ref-ruling> E. 1b; <ref-ruling> E. 1, je mit Hinweisen).
1. Der Beschwerdeführer ist als Partei des kantonalen Verfahrens ohne weiteres legitimiert, mit staatsrechtlicher Beschwerde geltend zu machen, das Appellationsgericht sei zu Unrecht auf seine Appellation nicht eingetreten (<ref-ruling> E. 1.4; <ref-ruling> E. 1b; <ref-ruling> E. 1, je mit Hinweisen).
2. 2.1 Der Beschwerdeführer wirft dem Verwaltungsgericht die Verletzung der Grundsätze von Treu und Glauben (<ref-law>) und des Vertrauensschutzes (<ref-law>) vor.
Er macht geltend, gemäss dem Urteil der Strafgerichtspräsidentin vom 14. Februar 2003 sei ihm das Appellationsrecht zugestanden. Gestützt darauf habe er innert 10 Tagen die Appellation erklärt und diese, nach Ausfertigung des schriftlich begründeten Urteils der Strafgerichtspräsidentin, innerhalb der vom Appellationsgericht angesetzten Frist ausführlich begründet. Aufgrund der falschen Rechtsmittelbelehrung dürfe ihm kein Nachteil erwachsen. Die Unrichtigkeit der Rechtsmittelbelehrung sei aufgrund des Wortlautes der Strafprozessordnung nicht ohne weiteres erkennbar gewesen. Er hätte diesen Fehler erst nach dem Studium der Gesetzesmaterialien und der Praxis des Appellationsgerichts feststellen können. Ein Blick in die Strafprozessordnung des Kantons Basel-Stadt, namentlich die Lektüre der §§ 94 und 174 Abs. 3, habe das fehlende Appellationsrecht nicht erkennen lassen. Die Praxis des Appellationsgerichts sei weder gebührend publiziert noch sonst in genügender Weise bekannt gemacht. In der Überzeugung, dass die Appellation das richtige Rechtsmittel sei, habe für ihn kein Anlass bestanden, den Vertrauensgrundsatz bereits vor Appellationsgericht anzurufen. Das Appellationsgericht hätte die Appellation deshalb beurteilen müssen.
2.2 Das Appellationsgericht weist im angefochtenen Entscheid darauf hin, dass das Verzeigungsverfahren gegen den Beschwerdeführer den Regeln der §§ 132 bis 140 StPO/BS unterstanden habe und kein ordentliches Verfahren im Sinne des Gesetzes darstellte. Der beanstandete Kostenentscheid der Strafgerichtspräsidentin sei daher nach <ref-law>//BS nicht appellabel, sondern lediglich beschwerdefähig gemäss §§ 184 ff. StPO/BS gewesen. Trotz des Verweises von <ref-law>/BS, wonach die Vorschriften der §§ 131 ff. StPO/BS sinngemäss gälten, werde das Verzeigungsverfahren nicht zu einem ordentlichen Verfahren. Da die am 24. Februar 2003 eingegangene Eingabe des Beschwerdeführers nicht begründet gewesen sei, könne sie nicht als Beschwerde entgegengenommen werden. Das Gericht führt in der Vernehmlassung zur staatsrechtlichen Beschwerde aus, es habe den Beschwerdeführer mit der Aufforderung zur Begründung der Appellation darauf aufmerksam gemacht, dass dieses Rechtsmittel möglicherweise nicht zulässig sei. Der Beschwerdeführer hätte daher bereits vor Appellationsgericht die Möglichkeit gehabt, sich auf den Vertrauensschutz und die Problematik einer falschen Rechtsmittelbelehrung zu berufen.
2.2 Das Appellationsgericht weist im angefochtenen Entscheid darauf hin, dass das Verzeigungsverfahren gegen den Beschwerdeführer den Regeln der §§ 132 bis 140 StPO/BS unterstanden habe und kein ordentliches Verfahren im Sinne des Gesetzes darstellte. Der beanstandete Kostenentscheid der Strafgerichtspräsidentin sei daher nach <ref-law>//BS nicht appellabel, sondern lediglich beschwerdefähig gemäss §§ 184 ff. StPO/BS gewesen. Trotz des Verweises von <ref-law>/BS, wonach die Vorschriften der §§ 131 ff. StPO/BS sinngemäss gälten, werde das Verzeigungsverfahren nicht zu einem ordentlichen Verfahren. Da die am 24. Februar 2003 eingegangene Eingabe des Beschwerdeführers nicht begründet gewesen sei, könne sie nicht als Beschwerde entgegengenommen werden. Das Gericht führt in der Vernehmlassung zur staatsrechtlichen Beschwerde aus, es habe den Beschwerdeführer mit der Aufforderung zur Begründung der Appellation darauf aufmerksam gemacht, dass dieses Rechtsmittel möglicherweise nicht zulässig sei. Der Beschwerdeführer hätte daher bereits vor Appellationsgericht die Möglichkeit gehabt, sich auf den Vertrauensschutz und die Problematik einer falschen Rechtsmittelbelehrung zu berufen.
3. 3.1 Zu den Grundsätzen rechtsstaatlichen Handelns gehört unter anderem die Verpflichtung der staatlichen Organe, nach Treu und Glauben zu handeln (<ref-law>). Zudem statuiert <ref-law> einen Anspruch des Einzelnen, von den staatlichen Organen nach Treu und Glauben behandelt zu werden. Welches die jeweilige Tragweite der beiden Grundsätze ist, braucht hier nicht entschieden zu werden, da der Beschwerdeführer beide Verfassungsbestimmungen anruft (zu dieser Diskussion vgl. <ref-ruling> E. 4.1; Beatrice Weber-Dürler, Neuere Entwicklung des Vertrauensschutzes, ZBl 103/2002, S. 281, 282 ff. mit Hinweisen; Christoph Rohrer, in: Die Schweizerische Bundesverfassung, Kommentar, St. Gallen 2002, Rz. 44 zu Art. 9).
3.2 Der Anspruch von Treu und Glauben schützt im Verhältnis zwischen Staat und Bürger vor allem das berechtigte Vertrauen in behördliche Zusicherungen und behördliches Verhalten (Yvo Hangartner, in: Die Schweizerische Bundesverfassung, Kommentar, St. Gallen 2002, Rz. 39 zu Art. 5). Die bundesgerichtliche Rechtsprechung hat aus dem Recht auf Vertrauensschutz (<ref-law>) den Grundsatz abgeleitet, dass einer Partei aus einer falschen Rechtsmittelbelehrung grundsätzlich kein Nachteil erwachsen darf. Diese Rechtsprechung steht allerdings unter dem Vorbehalt, dass sich nur auf eine fehlerhafte Rechtsmittelbelehrung berufen kann, wer deren Unrichtigkeit nicht kennt und auch bei gebührender Aufmerksamkeit nicht hätte kennen können. Allein grobe Fehler einer Partei oder ihres Rechtsvertreters sollen aber dazu führen, eine falsche Rechtsmittelbelehrung aufzuwiegen. Das Bundesgericht hat in seiner bisherigen Rechtsprechung einen solchen Fehler bejaht und den Vertrauensschutz dementsprechend versagt, wenn eine Partei oder ihr Anwalt die Fehlerhaftigkeit der Rechtsmittelbelehrung allein durch Konsultieren des massgebenden Gesetzestextes hätte erkennen können. Nicht verlangt wird hingegen, dass neben dem Gesetzestext auch noch die einschlägige Literatur oder Rechtsprechung hätte nachgeschlagen werden müssen (<ref-ruling> E. 2c S. 205 mit Hinweisen).
3.3 Im Kanton Basel-Stadt wird ein im Verzeigungsverfahren gemäss §§ 132 ff. StPO/BS ergangener Strafbefehl durch die Einsprache aufgehoben. Der Fall geht dann an das Strafgericht zur Durchführung der Hauptverhandlung (<ref-law>/BS). Gemäss der Strafprozessordnung des Kantons Basel-Stadt ist das Verzeigungsverfahren ein besonderes Verfahren (vgl. den Titel vor §§ 132 ff. StPO/BS). Das Verfahren der Hauptverhandlung richtet sich jedoch auch im Verzeigungsverfahren sinngemäss nach den Bestimmungen der §§ 113 ff. StPO/BS, d. h. nach den Vorschriften des ordentlichen Verfahrens auf öffentliche Klage (vgl. den Titel vor §§ 94 ff. StPO/BS), soweit nichts anderes bestimmt wird. Nach der Hauptverhandlung erfolgt die Verkündung des Urteils mit einer kurzen Begründung. Gleichzeitig sind die Parteien über das ihnen allfällig zustehende Appellationsrecht zu belehren (<ref-law>/BS).
Gegen Strafurteile können Verurteilte appellieren, wenn eine Freiheitsstrafe oder eine Geldbusse von wenigstens Fr. 500.-- oder eine andere beschwerende Verfügung gegen sie ausgesprochen wurde (<ref-law>/BS). Bei Freispruch oder Einstellung im ordentlichen Verfahren können Beurteilte die Appellation erklären, wenn sie durch die Motive des Urteils oder die Auferlegung von Kosten beschwert sind (<ref-law>/BS).
3.4 Der Beschwerdeführer wurde von der Strafgerichtspräsidentin am 14. Februar 2003 freigesprochen. Sie auferlegte ihm jedoch die Verfahrenskosten. Der Entscheid wurde mit dem Hinweis auf das Appellationsrecht eröffnet.
Allein aufgrund der Konsultation der Strafprozessordnung wird nicht sogleich klar, welches im Verzeigungsverfahren das zutreffende Rechtsmittel gegen die Kostenauflage nach der in sinngemässer Anwendung der Regeln über das ordentliche Verfahren durchgeführten Hauptverhandlung ist. Dass der Verweis von <ref-law>/BS nicht auch für die Anfechtung der Kostenauflage nach der Hauptverhandlung gilt, drängt sich aufgrund des Gesetzestextes nicht auf. Für den Beschwerdeführer bestand alleine gestützt auf den Wortlaut der Strafprozessordnung kein Anlass, an der Richtigkeit der Rechtsmittelbelehrung zu zweifeln. Dies gilt namentlich auch aufgrund von <ref-law>/BS, wonach "die Parteien über das ihnen allfällig zustehende Appellationsrecht" zu belehren sind. Vom Beschwerdeführer bzw. von seinem Vertreter wird nicht verlangt, dass er die Gesetzesmaterialien oder die Praxis des Appellationsgerichts konsultiert (vgl. E. 3.2 hiervor). Anscheinend war auch im Kreis des Strafgerichts Basel-Stadt nicht bekannt, dass gegen die Kostenauflage einzig die Beschwerde zur Verfügung stand; den diesbezüglichen Ausführungen des Beschwerdeführers in der staatsrechtlichen Beschwerde wurde jedenfalls nicht widersprochen. Ein grober Fehler, wie ihn die bundesgerichtliche Rechtsprechung verlangt, damit die falsche Rechtsmittelbelehrung aufgewogen würde, kann dem Beschwerdeführer bzw. seinem Vertreter jedenfalls nicht vorgeworfen werden. Zudem war die Unrichtigkeit der Rechtsmittelbelehrung offenbar auch für das Appellationsgericht nicht derart offenkundig, dass auf die Einholung der Appellationsbegründung sowie einer Appellationsantwort verzichtet worden wäre (vgl. dazu <ref-law>/BS).
Da der Beschwerdeführer vor Appellationsgericht der Meinung war, die Appellation sei das korrekte Rechtsmittel, hatte er keinen Anlass, sich bereits in der Appellationsbegründung auf den Vertrauensschutz zu berufen; daran vermag die Begründung zur Verfügung des Appellationsgerichts vom 26. August 2003 nichts zu ändern. Das Appellationsgericht hätte unter den vorliegenden Umständen den Vertrauensschutz (Treu und Glauben) von Amtes wegen beachten sollen. Entgegen den Ausführungen des Appellationsgerichts in der Vernehmlassung führt die Anrufung des Vertrauensgrundsatzes auch nicht zur Schaffung eines gesetzlich nicht vorgesehenen Rechtsmittels (vgl. dazu <ref-ruling> E. 1.5 S. 201 mit Hinweisen). Der Beschwerdeführer ergriff lediglich das unzutreffende Rechtsmittel. Dass das Urteil der Strafgerichtspräsidentin mit Beschwerde anfechtbar gewesen wäre, führt das Appellationsgericht in seinem Entscheid vom 5. Dezember 2003 selber aus.
Da der Beschwerdeführer vor Appellationsgericht der Meinung war, die Appellation sei das korrekte Rechtsmittel, hatte er keinen Anlass, sich bereits in der Appellationsbegründung auf den Vertrauensschutz zu berufen; daran vermag die Begründung zur Verfügung des Appellationsgerichts vom 26. August 2003 nichts zu ändern. Das Appellationsgericht hätte unter den vorliegenden Umständen den Vertrauensschutz (Treu und Glauben) von Amtes wegen beachten sollen. Entgegen den Ausführungen des Appellationsgerichts in der Vernehmlassung führt die Anrufung des Vertrauensgrundsatzes auch nicht zur Schaffung eines gesetzlich nicht vorgesehenen Rechtsmittels (vgl. dazu <ref-ruling> E. 1.5 S. 201 mit Hinweisen). Der Beschwerdeführer ergriff lediglich das unzutreffende Rechtsmittel. Dass das Urteil der Strafgerichtspräsidentin mit Beschwerde anfechtbar gewesen wäre, führt das Appellationsgericht in seinem Entscheid vom 5. Dezember 2003 selber aus.
4. Nach dem Gesagten ist die staatsrechtliche Beschwerde gutzuheissen und das angefochtene Urteil des Appellationsgerichts des Kantons Basel-Stadt aufzuheben.
Bei diesem Ausgang des Verfahrens sind keine Kosten zu erheben (Art. 156 Abs. 2 OG). Der Kanton Basel-Stadt hat dem Beschwerdeführer für das bundesgerichtliche Verfahren eine angemessene Parteientschädigung zu bezahlen (Art. 159 Abs. 1 OG).

Demnach erkennt das Bundesgericht:
Demnach erkennt das Bundesgericht:
1. Die staatsrechtliche Beschwerde wird gutgeheissen und das Urteil des Appellationsgerichts des Kantons Basel-Stadt, Ausschuss, vom 5. Dezember 2003 aufgehoben.
1. Die staatsrechtliche Beschwerde wird gutgeheissen und das Urteil des Appellationsgerichts des Kantons Basel-Stadt, Ausschuss, vom 5. Dezember 2003 aufgehoben.
2. Es werden keine Kosten erhoben.
2. Es werden keine Kosten erhoben.
3. Der Kanton Basel-Stadt hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen.
3. Der Kanton Basel-Stadt hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen.
4. Dieses Urteil wird dem Beschwerdeführer, der Strafgerichtspräsidentin des Kantons Basel-Stadt und dem Appellationsgericht des Kantons Basel-Stadt, Ausschuss, schriftlich mitgeteilt.
Lausanne, 2. September 2004
Im Namen der I. öffentlichrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: