4.3.3.1 - Reverse Polish and infix expressions (C#)

Infix and reverse Polish forms

Infix notation places a binary operator between its operands, such as a + b. Reverse Polish notation (RPN), also called postfix notation, places the operator after both operands: a b +.

An operand can be a whole sub-expression. In (a + b) * c, the addition must be evaluated before multiplication. Its RPN is a b + c *: first a and b supply the addition, then its result and c supply the multiplication. No brackets are needed because every operator consumes the preceding completed operands. In contrast, a + b * c becomes a b c * +; multiplication creates the second operand of the addition.

RPN is suitable for stack-based evaluation. Some interpreters and virtual-machine instruction systems use this operand-stack idea; PostScript is a stack-based language, and stack-oriented bytecode instructions consume operands from a stack. This is a use of RPN's structure, not a claim that all bytecode or all interpreters use one architecture.

Evaluating with a stack

Read an RPN expression from left to right, pushing operands and replacing the top two operands with each operator's result. Pop the right operand first, then the left operand: the later operand is on top of a last-in, first-out stack.

For 12 3 2 + /, the stack below shows its bottom on the left.

Use a numeric type suited to the task: C# integer division would produce 2 for 12 / 5, whereas double division produces 2.4. A valid complete binary-operator expression leaves exactly one result; an operator with fewer than two pending operands is invalid.

This C# method evaluates valid space-tokenised expressions containing numbers, + and -. InvariantCulture makes the decimal point convention explicit. Every input is guaranteed valid, so the method need not invent additional input validation.

using System.Collections.Generic;
using System.Globalization;
class Program
{
    static double Evaluate(string[] tokens)
    {
        Stack<double> values = new Stack<double>();
        foreach (string token in tokens)
        {
            if (token == "+" || token == "-")
            {
                double right = values.Pop();
                double left = values.Pop();
                values.Push(token == "+" ? left + right : left - right);
            }
            else
                values.Push(double.Parse(token, CultureInfo.InvariantCulture));
        }
        return values.Pop();
    }
}

For 9 4 - 2 +, the intermediate result is 5 and the final result is 7. Subtraction is a useful test because reversing operands changes the result; addition alone cannot reveal that error.