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. § 35 Abs. 3 StPO/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. § 174 Abs. 3 StPO/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 Art. 5 Abs. 3 BV (Grundsatz von Treu und Glauben) und Art. 9 BV (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. 