Computers need the order made explicit
People read 12 + 3 * 4 and know that multiplication happens first. A left-to-right calculation would incorrectly produce 60 instead of 24. Parentheses, precedence and associativity make infix notation comfortable for humans but force a program to remember operators whose execution must wait.
This system uses one stack during conversion and a second stack during evaluation. The conversion phase produces postfix notation, where an operator appears after its operands. Postfix 12 3 4 * + needs no parentheses and can be evaluated with one linear scan.
Parse
Recognise multi-digit integers, operators and parentheses.
Convert
Use an operator stack to create postfix order.
Evaluate
Use a value stack and reject unsafe operations.
Define the accepted language before coding
| Element | Accepted form | Example |
|---|---|---|
| Operands | Non-negative, multi-digit integers | 0, 7, 125 |
| Grouping | Balanced round parentheses | (12 + 3) |
| Operators | + − * / % ^ | 8 % 3 |
| Whitespace | Optional between tokens | 10+2 and 10 + 2 |
| Division | C integer division | 7 / 2 = 3 |
| Excluded | Unary minus and decimal operands | −5 and 2.5 rejected |
Precedence and associativity
| Operators | Precedence | Associativity |
|---|---|---|
| ^ | 3 · highest | Right-to-left |
| * / % | 2 | Left-to-right |
| + − | 1 · lowest | Left-to-right |
2 ^ 3 ^ 2 means 2 ^ (3 ^ 2), while 20 - 5 - 3 means (20 - 5) - 3.Two stacks solve two different problems
OperatorStack
Stores operators and opening parentheses that cannot yet be emitted. The top holds the next candidate for postfix output.
ValueStack
Stores already evaluated partial results. Every binary operator consumes the top two values and pushes one result.
Operator stack during conversion: [ (, +, * ] Value stack during evaluation: [ 12, 20, 3 ]
Conversion invariants
- Every processed operand already appears in postfix output exactly once.
- Operators still on the stack are waiting for a right operand, a closing parenthesis or a lower-priority incoming operator.
- An opening parenthesis is never copied into postfix; it is only a boundary marker.
expectOperandtells whether the next valid token is an operand/(or an operator/).
Evaluation invariant
After processing any valid postfix prefix, the value stack contains exactly the completed subexpression results that have not yet been consumed. A valid full expression finishes with one—and only one—value.
The shunting-yard decision at each token
| Incoming token | Action |
|---|---|
| Number | Copy the complete number to postfix |
| ( | Push it as a grouping boundary |
| ) | Pop to postfix until matching ( is removed |
| Operator | Pop stronger operators; also pop equal left-associative operators; then push incoming operator |
| End | Pop remaining operators; reject any remaining ( |
The precise pop condition
pop while top is not '(' and
(precedence(top) > precedence(incoming) or
same precedence and incoming is left-associative)For a right-associative incoming ^, an equal ^ remains on the stack. That single exception preserves 2 ^ (3 ^ 2).
Token boundaries
Postfix output separates tokens with spaces. Without delimiters, 12 3 + could be confused with 1 23 +. The parser scans all consecutive digits before emitting a number.
Operand order is easy to reverse accidentally
- When a number appears, push it.
- When a binary operator appears, pop right first and then left.
- Compute
left operator right. - Push the result.
- At the end, require exactly one stack value.
Postfix: 20 5 3 - / Push 20, 5, 3 → '-' pops right=3, left=5 → push 2 '/' pops right=2, left=20 → push 10
Reversing the two pops would calculate 3−5 and then −2/20. Addition hides this bug because it is commutative; subtraction and division expose it.
Compiler-ready C11 program
The program uses fixed-capacity array stacks so the push/pop mechanics remain visible. It validates token order while converting rather than accepting malformed input and hoping evaluation catches it later.
Loading source…Important implementation choices
Bounded arrays
Every push checks capacity; postfix appends check the output buffer.
Integer power
Exponentiation by squaring avoids a non-standard dependency and runs in O(log exponent).
Copy before strtok
Evaluation tokenises a copy so the printable postfix expression remains unchanged.
Trace: 12 + 3 × (8 − 2) ^ 2
- The first multi-digit operand is emitted.
- Plus waits for its right operand.
- The next operand is emitted.
- Multiplication waits above addition.
- Opening parenthesis creates a boundary.
- Tokens inside the group are processed.
- The parenthesised expression is closed.
- Power waits with the highest precedence.
- All remaining operators are emitted.
- The value stack produces the final result 120.
Press Next to begin.
Test grammar, precedence and runtime errors separately
| Expression | Expected result | Purpose |
|---|---|---|
| 42 | 42 | Single operand |
| 12 + 3 * 4 | 24 | Precedence |
| (12 + 3) * 4 | 60 | Parentheses override |
| 20 - 5 - 3 | 12 | Left associativity |
| 2 ^ 3 ^ 2 | 512 | Right associativity |
| 7 / 2 | 3 | Integer division |
| 12 / (3 - 3) | Error | Division by zero |
Malformed token order
2 3, 2 + * 3, + 4 and 7 - must each produce a useful validation error.Unbalanced parentheses
(2+3 and 2+3). One leaves an opening marker; the other cannot find a matching opening marker.Unsupported forms
-5+2, 2.5+1 and A+3 must be rejected according to the documented grammar.Capacity boundary
Every token is pushed and popped at most once
| Phase | Time | Space | Reason |
|---|---|---|---|
| Token scan | O(n) | O(n) | Read each character |
| Infix → postfix | O(n) | O(n) | Each operator pushed/popped once |
| Postfix evaluation | O(n) | O(n) | Each token processed once |
| Integer power | O(log e) | O(1) | Exponentiation by squaring |
| Complete pipeline | O(n + Σlog e) | O(n) | Expression plus power operations |
A recursive-descent parser can evaluate infix directly and produces a clearer syntax tree for richer languages. The two-stack design is ideal here because it exposes stack behaviour, precedence and associativity with a compact implementation.
Check the decisions behind the algorithm
When evaluating postfix 8 3 -, which value is popped first?
Why does incoming ^ not pop an equal ^?
Build the next version
- Add unary minus by distinguishing prefix
-from binary subtraction. - Support decimal operands and define division/rounding semantics.
- Add variables and a symbol table:
total = price * quantity. - Construct an expression tree from postfix and print prefix, infix and postfix traversals.
- Detect signed-integer overflow for every arithmetic operation.
Explain the algorithm—not only the output
Why is postfix easier to evaluate?
The order of execution is encoded directly in token order. When an operator appears, its operands are already available, so parentheses and precedence checks are unnecessary.
Why are two stacks used?
The operator stack resolves future execution order during conversion. The value stack combines already available operands during evaluation. Their elements and invariants are different.
How do parentheses work?
An opening parenthesis is pushed as a boundary. A closing parenthesis pops operators until that boundary, then removes the opening marker without emitting either parenthesis.
What makes the conversion O(n)?
Although an operator may trigger several pops, each operator is pushed once and popped once across the full scan. The total stack work is therefore linear.
How would you support functions such as max(2,5)?
The tokenizer must recognise names and commas; the conversion algorithm must track function tokens and argument separators; evaluation must know each function’s arity.
A stack stores decisions that cannot be completed yet
The operator stack postpones execution until precedence permits it; the value stack postpones partial results until an operator needs them. By defining the grammar, invariants, error cases and token order explicitly, the project turns a familiar calculator into a rigorous data-structure application.