From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=0.6 required=5.0 tests=BAYES_20,INVALID_MSGID
	autolearn=no autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,cae702701e24ef29
X-Google-Attributes: gid103376,public
From: jm59@prism.gatech.edu (John M. Mills)
Subject: Re: Please read this..thank you
Date: 1997/11/10
Message-ID: <64785j$cjg@acmex.gatech.edu>#1/1
X-Deja-AN: 288903521
References: <345BBEC0.1D12@upnaway.com> <346335F8.7B04@lmco.com>
Organization: Georgia Institute of Technology
Newsgroups: comp.lang.ada
Date: 1997-11-10T00:00:00+00:00
List-Id: <comp.lang.ada>


"Howard W. LUDWIG" <howard.w.ludwig@lmco.com> writes:

>Sho wrote:
>> Could you please help me with the algorithms on how to convert Infix to
>> a Postfix expression? examples:
>> 
>> Infix: 1 + 2 + 3
>> Postfix: 1 2 3 + +

>I do not know whether you were simply trying to put together a quick, 
>simple example without paying close attention to what you were doing ..

As a side comment to Mr. Ludwig's reply, this illustrates (to me) how we
become so habituated to an activity [like parsing arithmetic expressions]
that we forget the underlying conventions we are using.  I used to assign
as an intro. problem to program a "simple" 4-function calculator, in order
that my students reflect on the gap behind habit and algorithm.

Most (including I) opted for a two-stack model: one to hold numeric
entry|result data and the second for operator tokens.  When an operator was
received, the code would compare it in precedence with the operator on top
of the operation stack, and either evaluate the appropriate number of
entry|result values, or add the new operator to the stack.  Postfix only
requires the entry|result stack, so far as I can recall: an operator can
always be applied when it is encountered in the input stream.  (Thus you
might say that H-P was able to sell half the expression-parsing problem to
the user. [;^)  Also, perhaps some more analytic reader can comment on
the uniqueness of the algebraic representation vs. postfix.  I think this
might have some subtlety, also.

To make sense of the algebraic-entry problem, we first need to make explicit
those implicit operators which have been omitted -- "(" and ")" in this
case.  Note the conversion from (say) " 1 2 3 * + "  to" 1 + 2 * 3 =" is a
bit more subtle.

Thanks, Sho, for an interesting question ...

-- 
John M. Mills, Senior Research Engineer   --   john.m.mills@gtri.gatech.edu
   Georgia Tech Research Institute, Georgia Tech, Atlanta, GA 30332-0834
        Phone contacts: 404.894.0151 (voice), 404.894.6258 (FAX)
           "Lies, Damned Lies, Statistics, and Simulations."