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]
}
}