# Powershell 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]
}
}
```