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.
raw
#
# 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.
raw
#
# 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.
raw
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:
raw
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.
raw
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]
}
}