RPN Expression Evaluator (C)
Topics: stacks, parsing, expression evaluation
Problem
Evaluate a space-separated reverse-Polish (postfix) expression of integers and
the four operators + - * /.
bool rpn_eval(const char *expr, long *out);
// true + *out on success; false on malformed input
For example, "5 1 2 + 4 * + 3 -" is the postfix form of 5 + (1 + 2) * 4 - 3, and
evaluates to 14.
Key concepts
- A stack is all you need. Scan tokens left to right. Push numbers. On an
operator, pop the top two values (the second one popped is the left operand),
combine them, and push the result. This is why postfix needs no parentheses and no
precedence rules: the order is already baked into the token sequence.
- A valid expression leaves exactly one value. If the stack does not end with
precisely one element, the input was malformed (too few or too many operands).
- Reject, do not crash. An operator with fewer than two operands (underflow),
division by zero, a token that is neither a number nor an operator, all return
false rather than doing something undefined.
- Sign subtlety: a single
- is the subtraction operator; -5 is a negative
literal. Distinguish them by token length.
The same stack machine, run on the output of a shunting-yard parser, is how
calculators and many bytecode VMs evaluate arithmetic.
Run
cc -std=c11 -O2 -Wall tests.c -o /tmp/rpn && /tmp/rpn
Sign in to submit your solution.