Postfix notation, also called Reverse Polish Notation (RPN), puts an operator after its operands. In a space-separated arithmetic expression, each operator uses the two most recent values. Reading from left to right removes the need for precedence rules. section 3.2
Infix: 3 + 4 * 12
RPN : 4 12 * 3 +
= 51
Infix: (3 + 4) * 12
RPN : 3 4 + 12 *
= 84
Compare the two infix expressions with their RPN forms: changing the order of the operators changes which calculation happens first. section 3.2
Evaluate with a stack
For `3 4 + 12 *`, push 3 and 4, then replace them with their sum, 7. Push 12; `*` replaces 7 and 12 with 84. For subtraction and division, operand order matters: pop the right operand first, then the left. section 3.2 section 3.2.3
A Rust evaluator can split the input into terms, parse integers onto a stack, and handle `+`, `-`, `*`, and `/` by popping two values and pushing the result. A failed integer parse or a pop from an empty stack returns an error. This lets a C calculator keep its input and output code while Rust handles expressions with multiple operations. section 3.2.3 section 3.2
Listing 3.9 Using evaluate for all four arithmetic operations
fn evaluate(problem: &str) -> Result<i32, Error> {
let mut stack = RpnStack::new();
for term in problem.trim().split(' ') {
match term {
"+" => {
let y = stack.pop()?;
let x = stack.pop()?;
stack.push(x + y);
}
"-" => {
let y = stack.pop()?;
let x = stack.pop()?;
stack.push(x - y);
}
"*" => {
let y = stack.pop()?;
let x = stack.pop()?;
stack.push(x * y);
}
"/" => {
let y = stack.pop()?;
let x = stack.pop()?;
stack.push(x / y);
}
other => match other.parse() {
Ok(value) => stack.push(value),
Err(_) => return Err(Error::InvalidNumber),
}
}
}
let value = stack.pop()?;
Ok(value)
}
The complete evaluator shows the same pop–calculate–push pattern for all four operators. section 3.2.3
