bookmark_borderPowershell Postfix to Infix

Here is a powershell example of converting an expression in postfix notation into infix notation. A little background on postfix notation, is that the operators follow the operands. For example “(1 + 2) = 1 2 +”. Postfix is much easier to interpret for a computer, since values are processed as they are used, and their is no need for parenthesis.

#
# Here is an example. 
# Postfix String: 1 2 - 3 * 4 * 5 - = -17
# Infix String:   ((((1 - 2) * 3) * 4) - 5) = -17
#

Here is an example of the algorithm followed by this example.

#
# Algorithm: For every item 'x' in the string
#    x -> number: push it onto the stack
#    x -> operator: pop two items of the stack, join them with x,
#                   then push the result back onto the stack.
#                   EX: "(stack.pop() x stack.pop())"
#
# Given the string "1 2 - 3 * 4 * 5 -"
#
# We use a stack to keep track of our progress.
#
# First item in the string = '1'
# '1' is a number so push it onto the stack
#
#  stack                  remaining: 2 - 3 * 4 * 5 -
#    1
#
# Next item in the string = '2'
# '2' is a number so push it onto the stack
#
#  stack                  remaining: - 3 * 4 * 5 -
#    2
#    1
#
# Next item in the string = '-'
# '-' is an operator, so pop two items of the stack, join, then push
#
#  stack                  remaining: 3 * 4 * 5 -
# (1 + 2)
#
# Next item in the string = '3'
# '3' is a number so push it onto the stack
#
#  stack                  remaining: * 4 * 5 -
#    3
# (1 + 2)
#
# Next item in the string = '*'
# '*' is an operator, so pop two items of the stack, join, then push
#
#  stack                  remaining: 4 * 5 -
# ((1 + 2) * 3)
#
# Next item in the string = '4'
# '4' is a number so push it onto the stack
#
#  stack                  remaining: * 5 -
#    4
# ((1 + 2) * 3)
#
# Next item in the string = '*'
# '*' is an operator, so pop two items of the stack, join, then push
#
#  stack                  remaining: 5 -
# ((1 + 2) * 3) * 4)
#
# Next item in the string = '5'
# '5' is a number so push it onto the stack
#
#  stack                  remaining: -
#    5
# ((1 + 2) * 3) * 4)
#
# Next item in the string = '-'
# '-' is an operator, so pop two items of the stack, join, then push

#  stack                  remaining:
# (((1 + 2) * 3) * 4) - 5)
#
# Now we just pop the last item off the stack, and we have our answer.

Here is the powershell which makes this all possible.

function PostfixTo-Infix
{
    param
    (
        [Parameter(Mandatory=$true)][string]$Postfix
    )
    process
    {
        # Split the string into the individual peices
        $values = $Postfix.Split(' ', [StringSplitOptions]::RemoveEmptyEntries)

        # Stack to store the values as they are being parsed
        $stack = [System.Collections.Generic.Stack[string]]::new()

        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($val)

                # Then continue on
                continue;
            }
            else
            {
                # The value is an operator, so pop off the previous two values,
                # And join them with the operator. 
                $b = $stack.Pop();
                $a = $stack.Pop();

                # Then push the result onto the stack
                $stack.Push("($a $val $b)")
            }
        }

        # The final item on the stack must be our result.
        return $stack.Pop()
    }
}

There you have it. Results look like this:

PostfixTo-Infix '1 2 - 3 4 * 5 + *'
((1 - 2) * ((3 * 4) + 5))

In the spirit of good programming, here is a code golfy powershell one liner which also works. It mostly uses the same principal, but uses a hashtable as the stack. One caveat is that it prints all results out backwards, which is fine because there are parenthesis everywhere.

function PostfixTo-InfixGolf
{
    param
    (
        [Parameter(Mandatory=$true)][string]$p
    )
    process
    {
        $s=@{};$a=0;switch -regex($p.Split(' ')){'\d'{$s[$a++]=$_}default{$t="($($s[--$a]) $_ $($s[--$a]))";$s[$a++]=$t}};$s[--$a]
    }
}

bookmark_borderPowershell Postfix Evaluator

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”.

#
# 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.

#
# 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.

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.

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.

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