Skip to main content

Infix to postfix and evaluation

Short answer

Stack is a LIFO structure. Infix to postfix: scan, output operands, push operators respecting precedence; brackets used. Evaluating AB+C*DEFG-*+ with given values: push operands; on operator, pop two, apply. Two values remain: 50 and 1 (expression lacks a final operator).

Define stack. How to convert infix to postfix notation? Explain with example. Evaluate the postfix expression AB+CDEFG-+ with status of stack where A = 2, B = 3, C = 10, D = 5, E = 2, F = 4 and G = 6.

A stack is a linear data structure in which insertion (push) and deletion (pop) take place only at one end called the top. The last element inserted is the first to be removed, so it follows LIFO (Last In First Out).

Converting infix to postfix

Postfix (reverse Polish) places each operator after its operands, so no parentheses or precedence rules are needed when evaluating. Rules with a stack:

  1. Scan the infix expression left to right.
  2. Operand: append it to the postfix output.
  3. (: push it on the stack.
  4. ): pop operators to the output until ( is found; discard both parentheses.
  5. Operator: while the stack top is an operator with higher or equal precedence (for ^, only higher, since ^ is right-associative), pop it to the output; then push the scanned operator.
  6. At the end, pop all remaining operators to the output.

Precedence (high to low): ^, then * /, then + -.

Example: (A + B) * C - D / E

StepSymbolStack (bottom → top)Postfix output
1((-
2A(A
3+(+A
4B(+AB
5)(empty)AB+
6**AB+
7C*AB+C
8--AB+C*
9D-AB+C*D
10/-/AB+C*D
11E-/AB+C*DE
end(pop all)(empty)AB+C*DE/-

Answer: AB+C*DE/-

Evaluating the postfix expression AB+C*DEFG-*+

Values: A=2, B=3, C=10, D=5, E=2, F=4, G=6. Rule: operand → push; operator → pop two (first pop is the right operand), apply, push the result.

StepSymbolActionStack (bottom → top)
1Apush 22
2Bpush 32, 3
3+pop 3 (right), 2 (left); 2 + 3 = 5; push5
4Cpush 105, 10
5*pop 10 (right), 5 (left); 5 * 10 = 50; push50
6Dpush 550, 5
7Epush 250, 5, 2
8Fpush 450, 5, 2, 4
9Gpush 650, 5, 2, 4, 6
10-pop 6 (right), 4 (left); 4 - 6 = -2; push50, 5, 2, -2
11*pop -2 (right), 2 (left); 2 * -2 = -4; push50, 5, -4
12+pop -4 (right), 5 (left); 5 + -4 = 1; push50, 1

Result: the single scan finishes with two values on the stack (50 and 1), because the expression as given has 7 operands but only 5 operators (6 are needed). The sub-results are (A+B)C = 50 and D + E(F−G) = 1. If the intended expression had one more operator at the end (for example +), the value would be 50 + 1 = 51.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 2 questions →