Arithmetic Expression EvaluationTaken from West Chester University web site:
This section illustrates two common stack-based algorithms for arithmetic expression manipulation:
- evaluating an arithmetic expression written in postfix form.
- converting an infix expression to postfix form.
Postfix expression evaluationIn the postfix expression evaluation algorithm, the stack contains only numbers. Here is a sketch of the algorithm: The arithmetic expressions 4 - ( 2 - 3 ) and 4 - 2 - 3 have these respective postfix expressions and evaluations: The arithmetic expression ( 7 + 3 ) * ( 11 - 4 * 2 ) has the following postfix form and evaluation:
Infix to Postfix conversionThe infix-to-postfix conversion algorithm is more complicated. It is extremely simple if all operators have the same precedence (such as "+" and "–") and there are no parentheses. Adding parentheses and operators of differing precedence introduces complications.
The goal of the algorithm is to construct an output string which is the equivalent postfix form of a given infix expression. The stack will hold operators and left parentheses. One key observation is that the numbers stay in the same order as in the infix expression.Here is a sketch of the algorithm: Observe in the way numbers are handled that the numbers appear in the same order as in the infix expression. Here are some examples:
Java ProgramsThese two programs are intended to be in the demo package.The Infix2Postfix program enters and processes an arithmetic expression (in standard infix form), generating an output of the arithmetic expression in postfix form. Operands are assumed to be unsigned non-negative integers.The PostfixEvaluation program evaluates a postfix expression. Again, operands are assumed to be unsigned non-negative integers.
Practice Problem 11 Solutions
- Convert: 19 - ( 7 - 4 * 3 + 2 ) * ( 7 - 5 ) Evaluate: 19 7 4 3 * - 2 + 7 5 - * -
- Convert: 3 - 7 * 15 / ( 2 + 3 )
- Convert: 17 - ( 22 - ( 11 - 8 + 2 ) )