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