Entry

Algorithm: How do you evaluate an infix expression?

Jul 9th, 2005 07:38
Knud van Eeden, Eric Astor, Peter Sim, Ben Udall, http://www.unimas.my/fit/tmc1433/lectures/stacks2/sld004.htm

----------------------------------------------------------------------
--- Knud van Eeden - 05 October 2020 - 20:37 -------------------------
---
Algorithm: Expression: Infix: How do you evaluate an infix expression?
An infix expression is an expression where the operator
is between the operands
e.g.
2 + 3
( i + 4 ) / 5
In case of an unary operator (like '-'), the operator
is in front.
---
Compare this e.g. with postfix, where the operator comes
after the operands
e.g.
2 3 +
i 4 + 5 /
---
and prefix where the operator comes
before the operands.
+ 2 3
/ 5 + i 4
===
A simple method to evaluate an infix expression is:
1. converting it to a postfix (or similarly prefix) expression.
   This removes the brackets, and uniquely fixes the order in which the
   characters have to be handled.
2. when finished reading, evaluate your result
---
--------------------------------------------------------------------
--- Eric Astor - 03 April 2021 - 17:39 -----------------------------
---
In addition, there is an alternate solution to this problem,
essentially a variation of the preceding answer.
Rather than carrying out the infix evaluation process in two steps,
the structures of a simple bracket-compatible infix-to-postfix
converter and a postfix evaluator are simple and compatible enough to
be merged into a single parser, using one stack each for operators and
answers.
In slightly more detail:
 1. Start with pretty much any simple infix-to-postfix converter
 2. Wherever an operand would be written to the string to be output,
    instead push it onto the answer stack.
 3. Wherever an operator would be written to the string to be output,
    instead pop its operands (right, then left) from the answer stack
    and store the result back onto the answer stack.
If at any time the answer stack runs empty when an operand is needed,
this indicates an invalid infix expression.
At the end, your result should be the only thing remaining in the
answer stack.
Otherwise, the original infix expression is invalid.
--------------------------------------------------------------------
Internet: see also:
---
Algorithm: Expression: Infix: Convert: Postfix: Overview: How convert 
infix to postfix expression?
http://www.faqts.com/knowledge_base/view.phtml/aid/26071/fid/585
---
Datastructure: Stack: Expression: Postfix: Evaluate: How do you
evaluate an RPN expression?
http://www.faqts.com/knowledge_base/view.phtml/aid/26059/fid/1279
----------------------------------------------------------------------