Powershell Infix to Postfix Conversion

A common programming problem and interview question is to take an equation in “infix” notation, and transform it into “postfix” notation.

Lets take this for example:
Infix: (1+2)*(3+4)
Postfix: 1 2 + 3 4 + *

There are a few cases to consider:

  • Numbers
  • Operators
  • Parenthesis

Numbers always appear in the same order which they are processed between infix and postfix, so not much special needs to happen there. Operators are a little more complicated,

Operators are a little more complex. They need to appear in the order which they should be evaluated. There are two things which affect this… parenthesis and the order of operations.

Take the example: 1 + 2 * 3. We always need the multiplication to be evaluated before the addition. There is a simple rule. Every time you encounter an operator, push it onto a stack. At the next operator, if the top of the stack is of greater value, then the stack can be emptied into the output. If the top of the stack is of the same or lesser value, then add the current operator to the stack. This ensures that we will always append the operators which come earlier in the order of operations first.

A walkthrough of 1 + 2 * 3 - 4

Token | Stack | Output
  1   |       |                 <- 1 is a number, can go directly to output
  +   |       |   1             <- + is an operator, and the stack is empty, so push it onto the stack
  2   |   +   |   1             <- 2 is a number, can go directly to output
  *   |   +   |  1 2            <- * is an operator, but the operator on the top of the stack is less important
  3   |  * +  |  1 2            <- 3 is a number, it can go directly to output
  -   |  * +  | 1 2 3           <- - is an operator, less important than '*' which is on top of the stack,
                                    so empty the stack, and add the '-' onto the stack
  4   |   -   | 1 2 3 * +       <- 4 is a number, it can go directly to output
      |   -   | 1 2 3 * + 4     <- We're out of tokens, so empty the stack
      |       | 1 2 3 * + 4 -

Parenthesis can just be handle recursively. When a parenthesis is encountered, everything on the inside should be processed and sent to the output before continuing forward.

A walkthrough of 1 * (2 + 3)

Token | Stack | Output
  1   |       |             <- 1 is a number, can go directly to output
  *   |       |   1         <- + is an operator, and the stack is empty, so push it onto the stack
  (   |   *   |   1             <- Hit a parenthesis, so recurse and process the inside
  
  2   |          |          <- 2 is a number, can go directly to the output
  +   |       |   2         <- + is an operator, and the stack is empty, so push it.
  3   |   +   |   2         <- 3 is a number, can go directly to output
  )   |   +   |  2 3        <- Hit a close parenthesis, so empty the stack and unwinde from recursion
      |       | 2 3 +  
  
      |   *   | 1 2 3 +     <- Append the result of the recursive call
      |       | 1 2 3 + *   <- We're out of tokens, to empty the stack into the output

Here is some poweshell which takes this approach.

#
# Converts an infix expression into a postfix style expression
#
function InfixTo-Postfix
{
    [CmdletBinding()]
    param
    (
        [Parameter(Mandatory=$true, ValueFromPipeline = $true)][String]$InfixString
    )

    process
    {
        # Queue of all of the tokens we split the input string into
        # Numbers, operators, parenthesis
        $tokenQueue = [System.Collections.Queue]::new();

        # To build up numbers, in case they are more than a single digit.
        $currentNumber = '';

        # Go through each chacter in the string, and split it into tokens
        foreach($c in $InfixString.ToCharArray())
        {
            if ([char]::IsDigit($c))
            {
                # Build up the current digit/number
                $currentNumber += $c;
            }
            else
            {
                # Enqueue the current number into the token queue.
                if ($currentNumber  -ne '')
                {
                    $tokenQueue.Enqueue($currentNumber);
                    $currentNumber = '';
                }

                # Anything else which isn't whitespace is an operator (or a variable: a*b)
                if (-not [char]::IsWhiteSpace($c))
                {
                    $tokenQueue.Enqueue($c);
                }
            }
        }
        
        # If theres anything in the number we're working on, add that as well.
        if ($currentNumber  -ne '')
        {
            $tokenQueue.Enqueue($currentNumber);
        }       

        # Define the supported operators
        # Give each operator a weight, following the order of operations.
        $operators = @{};
        $operators[[char]'^'] = 2;
        $operators[[char]'*'] = 1;
        $operators[[char]'/'] = 1;
        $operators[[char]'+'] = 0;
        $operators[[char]'-'] = 0;

        # Helper function to handle everything underneath a set of parenthesis
        # Assumes that the open parenthsis has been removed from the token queue.
        function HandleParenthesis
        {
            # The output queue, this is where we'll write the result.
            $outQueue = @();

            # The operator stack.
            $operatorStack = [System.Collections.Stack]::new();

            # When the token queue is not empty
            while ($tokenQueue.Count -gt 0)
            {
                # Take the next item from the queue
                $item = $tokenQueue.Dequeue();
                
                if ($item -eq '(')
                {
                    # If it is an open parenthesis, we shoudl recurse.
                    $outQueue += HandleParenthesis
                }
                elseif ($item -eq ')')
                {
                    # On a close parenthesis, we're all done.
                    break;
                }
                elseif($operators.ContainsKey($item))
                {
                    # On an operator. Check to see if the top operator on the stack has a higher value than the current one.
                    # For example, if a '+' follows a '*', we need to do the '*' before the '+'.
                    if ($operatorStack.Count -gt 0 -and $operators[$operatorStack.Peek()] -gt $operators[$item])
                    {
                        while ($operatorStack.Count -gt 0)
                        {
                            $outQueue += $operatorStack.Pop();
                        }
                    }

                    # Push the current operator onto the stack
                    $operatorStack.Push($item);
                }
                else
                {
                    # Anything else, just append to the output.
                    $outQueue += $item;
                }
            }

            # If we have read all of the tokens we need to read, but there are still operators on the stack, finish popping them off.
            while ($operatorStack.Count -gt 0)
            {
                $outQueue += $operatorStack.Pop();
            }

            # Return the output.
            return $outQueue
        }   

        # Proecess the equation
        $outQueue = HandleParenthesis

        # The output queue is an array, so just turn it into a string
        return ($outQueue -join ' ');
    }
}
InfixTo-Postfix "x ^ y / (5 * z) + 10"
InfixTo-Postfix "(1+2)*(3+4)"
InfixTo-Postfix "1 ^ 2 ^ 3 ^ 4 ^ 5 * 6"

x y ^ 5 z * / 10 +
1 2 + 3 4 + *
1 2 3 4 5 ^ ^ ^ ^ 6 *

While we’re here lets do some golf.

function InfixTo-PostfixGolf($i){Set-Variable q -Value([regex]'([\d]+)|([\(\)\S])').Matches($i).Value -Option AllScope;function F{$o=@();$s=@();$e=@{'-'=0;'+'=0;'/'=1;'*'=1;'^'=2;};while($q){$t,$q=$q;switch($t){'('{$o+=F}')'{return $o+$s}({$e.ContainsKey($t)}){if($s-and$e[$s[0]]-gt$e[$t]){$o+=$s;$s=@()}$s=,$t+$s;}default{$o+=$t}}}$o+$s}(F)-join' '}

That’s 351 characters. It definitely seems like a sub-par solution, so I’ll be back.

It’s important to note that this solution takes a recursive approach to handling parenthesis. Another option is to push the parenthesis onto the stack, and use them as barriers when popping off operators. Aka, pop until you get back to the open parenthesis.

Leave a Reply

Your email address will not be published. Required fields are marked *