There are three different notations for expressing a mathematical equation.

  • prefix
  • infix
  • postfix

Basically, the just describe where operators lie in the equation compared to their operands. The most common of all of the formats is the one everyone is probably most familiar with, infix, which means that the operators lie in between their operands. Lets take for example the equation "1 + 5".

raw

#
# Equation: "1 + 5"
#
#  Prefix:  "+ 1 5"
#  Infix:   "1 + 5"
#  Postfix: "1 5 +"
#

From the perspective of a computer, postfix if very easy to process, because an operator always follows its two operands, and their is no reason to use parenthesis. Prefix notation also does not require parenthesis, but is a little strange to work with.

In order to process prefix, we always take the right most operator in the expression, and apply it to the next two digits in the string. We do that until we are out of operators. Infix is processed using the order of operations. Postfix is processed by taking the left most operand in the expression, and applying it to the preceding digits every time.

raw

#
# Equation1: "(1 + 5) * 3"
# Equation2: "1 + 5 * 3"
#
#  Prefix1:  "* + 1 5 3"   => "* 6 3"   => "18"
#  Infix1:   "(1 + 5) * 3" => "(6) * 3" => "18"
#  Postfix1: "3 1 5 + *"   => "3 6 *"   => "18"
#
#
#  Prefix2:  "+ * 3 5 1"   => "+ 15 1"  => "16"
#  Infix2:   "1 + 5 * 3"   => "1 + 15"  => "16"
#  Postfix2: "1 5 3 * +"   => "1 15 +"  => "16"
#

The postfix algorithm is quite simple to implement. Going through the string, every time you see a number, add it to a stack. If you see an operator, pop the last two items off of the stack and apply the operator. Push the result back onto the stack so that it can be used in following computations.

So here is an example of the postfix algorithm implemented in powershell.

raw

function Eval-Postfix
{
    param
    (
        [Parameter(Mandatory = $true)][string]$expression
    )
    process
    {
        # Create a stack to store the numbers which aren't yet processed
        $stack = [System.Collections.Generic.Stack[int]]::new()

        # Split the input string into individual values
        $values = $expression.Split(' ', [System.StringSplitOptions]::RemoveEmptyEntries)

        foreach($val in $values)
        {
            # Try to parse the value
            $intvalue = 0
            if([int]::TryParse($val, [ref]$intvalue))
            {
                # If the value is an integer, add it to the stack
                $stack.Push($intvalue)

                # Then continue on
                continue;
            }

            # If the value is not an integer, we pop the top two numbers off the stack
            $b = $stack.Pop()
            $a = $stack.Pop()

            # Then perform the correct operation on them
            $result = switch($val)
            {
                '+' { $a + $b; break; }
                '-' { $a - $b; break; }
                '*' { $a * $b; break; }
                '/' { $a / $b; break; }
            }

            # Push the result back onto the stack
            $stack.Push($result)
        }

        # The only thing left on the stack should be a single value,
        # which is the result of the final operation
        return $stack.Pop()
    }
}

Just to be safe, here is code golf one liner which uses the same queue approach to solve the problem.

raw

function Eval-Postfix
{
    param
    (
        [Parameter(Mandatory = $true)][string]$e
    )
    process
    {
        $s=@();switch -regex($e.Split(' ')){'\d'{$s=,+$_+$s}default{$a,$b,$s=$s;$s+=iex "$b$_$a"}};$s
    }
}

The code golf version uses a powershell array rather than a stack, and uses a switch as a loop. There you have it, both of these functions will output the results of postfix operations.

raw

#
#  > Eval-Postfix3 "1 2 + 5 6 * +"
#     33
#