4.3.3.1 - Reverse Polish and infix expressions (VB.NET)

Infix and postfix forms

Infix puts a binary operator between its two operands, while Reverse Polish notation puts it after them.

An operand is a value or a whole sub-expression used by an operator. Work from the grouping of the infix expression, not simply from its printed sequence. In $(A+B)\times C$, the sum is the left operand of multiplication. First express the sum as A B +, then append C and *, giving A B + C *. In $A+B\times C$, multiplication has precedence; its postfix form is A B C * +.

RPN needs no brackets to say which operation comes first. Each binary operator uses the two completed operands immediately available to it; the order of tokens carries the grouping. Subtraction and division must keep left and right operands in their original positions.

Evaluating RPN with a stack

An RPN evaluator keeps completed operand values on a stack until an operator needs them.

Read tokens from left to right. Push a number. At a binary operator, pop the right operand first, then the left operand, calculate left operator right and push the result. The last number pushed is the second operand, not the first.

For 12 3 1 + /, the trace is:

At /, the first pop is 4 and the second is 12, so the calculation is $12/4=3$. A valid complete expression leaves exactly one value. A binary operator needs two values already on the stack; an incomplete expression may underflow the stack or leave spare values.

This native evaluator assumes valid space-separated tokens, operators +, -, *, /, decimal points written with ., and no division by zero. Validation is outside this example's contract. Put the function inside a module, with Imports System.Collections.Generic.

Function Evaluate(tokens As String()) As Double
    Dim values As New Stack(Of Double)()
    For Each token As String In tokens
        If token = "+" OrElse token = "-" OrElse
           token = "*" OrElse token = "/" Then
            Dim right As Double = values.Pop()
            Dim left As Double = values.Pop()
            Select Case token
                Case "+" : values.Push(left + right)
                Case "-" : values.Push(left - right)
                Case "*" : values.Push(left * right)
                Case "/" : values.Push(left / right)
            End Select
        Else
            values.Push(Double.Parse(token, Globalization.CultureInfo.InvariantCulture))
        End If
    Next
    Return values.Pop()
End Function