Please read this..thank you

Please read this..thank you

[Sho]

Dear Ada Programmers,

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 + +

If anyone has done a program that converts infix to postfix could you
please help me via email or newsgroup? Thank you for your time and
consideration.^_^

Sho

Re: Please read this..thank you

[Robert S. White]

In article <345BBEC0.1D12@upnaway.com>, Sho@upnaway.com says...
>
>Dear Ada Programmers,
>
>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 + +

  The most common technique (for this very old homework problem) is
to push operations up on one stack and data up on another while
examining the precedence of the must recently pushed operation with
the newest encountered operation - and immediately doing the operation
if appropriate.  I remember helping people with their Pascal homework
on this type of problem in the early 80's.  I hope you can take this 
general approach and flesh it out to code the solution to your problem.

>If anyone has done a program that converts infix to postfix could you
>please help me via email or newsgroup? 

  We really should not do this - although I am sure that I have seen
such programs in learning to program books.  For example check out 
Michael Feldman's book "Ada 95 Problem Solving and Program Design" 
in chapter 14.6 Problem Solving: Stacks and Queues around page 683 
he has an example, CHECKING FOR BALANCED PARANTHESES, which uses 
stacks that should give you some clues and useful code snippets.

Thank you for your time and
>consideration.^_^

  Good luck, work hard, and have fun :-)
_____________________________________________________________________
Robert S. White         -- An embedded systems software engineer
e-mail reply to reverse of: ia us lib cedar-rapids crpl shift2 whiter

Re: Please read this..thank you

[Howard W. LUDWIG]

Sho wrote:
> 
> Dear Ada Programmers,
> 
> 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 
(and consequently made a silly mistake) or you have an actual 
misunderstanding which may cause you troubles in trying to compose 
appropriate code.  However, your example is in error:

While we all know that addition of integers (and, more generally, real 
and complex numbers) is associative, so that (1 + 2) + 3 = 1 + (2 + 3).  
However, most applications (APL being the only major exception I know) 
regard 1 + 2 + 3 as meaning (1 + 2) + 3 (which might be modified by 
application of commutative and associative principles to some other 
arrangement--note that Ada is restrictive regarding such rearrangements 
for floating point values due to the "non-real" floating-point model, 
so I am not being pedantic here; another example would be an operation, 
such as subtraction, which is nonassociative).   Now,
   (1 + 2) + 3  is  1 2 + 3 +  in infix
whereas
   1 + (2 + 3)  is  1 2 3 + +  in infix.
 
> Sho

Howard W. LUDWIG
Working (but not speaking) for Lockheed Martin Electronics & Missiles
Co.

Re: Please read this..thank you

[John M. Mills]

"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."