# Converting from postfix to infix

What would be a good algorithm for converting from postfix to infix? I've searched and searched but I only get algorithms for converting from infix to postfix. They're going to be decently similar algorithms correct? I also want to incorporate parenthesis. For example, (((13 - 1) / 2)(3 + 5)). Thank you!

• Maintain a stack 1. if you read a value push it to stack 2. if you read an operator, pop 2 values(say a,b) and push "(a operator b)" back to stack Seems like it will do – Sunny Agrawal Sep 27 '13 at 14:24

Here's the postfix version:-

``````13 1 - 2 / 3 5 + *
``````

To convert, parse it like an ordinary postfix parser, but store elements on the stack as a string, not as values:-

``````"13"
"1"
"-"
``````

when you get an operator, like above, convert to a single string and put parenthesis around it:-

``````"(13-1)"
``````

continuing:-

``````"(13-1)"
"2"
"/"
``````

becomes:-

``````"((13-1)/2)"
``````

continuing:-

``````"((13-1)/2)"
"3"
"5"
"+"
``````

becomes:-

``````"((13-1)/2)"
"(3+5)"
``````

finally:-

``````"((13-1)/2)"
"(3+5)"
"*"
``````

ends up as:-

``````"((13-1)/2)*(3+5)"
``````

you could treat "*" as a special case and omit it from the combined version.

We start with an empty stack. Assuming the postfix expression is correct :

• Read the atomic tokens and put them on stack
• when you reach an operator, pop n elements from the stack where n is the arity of the operator, format it correctly, put the brackets around it and push the resolution back to the stack
• when there's nothing to read, the stack should contain exactly one element with the result

For instance :

input : `2,3,+,5,-,8,*`

Stack contains after each step :

`````` 2
2,3
(2+3)
(2+3),5
((2+3)-5)
((2+3)-5),8
(((2+3)-5)*8)
``````

This would be my approach

``````while(input.hasNext()) {
if (symbol is operand) {
stack.push(symbol)
} else { // the symbol is an operator
if (stack.count < 2) {
ERROR too few operands
} else {
op2 = stack.pop();
op1 = stack.pop();
piece = "("+op1+symbol+op2+")";
stack.push(piece);
}
}
}

if (stack.count == 1) {
stack.pop() is the INFIX
} else {
ERROR
}
``````

Of course if you want to consider unary operators, the conditions have to be a little more structured to consider the stack with a single element

Here is a full Ruby implementation of the algorithm mentioned:

``````#!/usr/bin/env ruby

parts = gets.strip.split(/ +/)

stack = [ ]

parts.each do |part|
if part =~ /\D/  # it's a binary operation
right_operand = stack.pop
left_operand = stack.pop
stack.push("(#{left_operand} #{part} #{right_operand})")
else             # it's a number
stack.push(part)
end
end

if stack.size == 1
result = stack[0][1..-2]  # remove outer parentheses
puts result
exit(0)
else
puts "parse error, stack does not contain exactly one element"
exit(1)
end
``````

Use like this:

``````echo '13 1 - 2 / 3 5 + *' | ruby postfix-to-infix.rb
``````

This example produces the result:

``````((13 - 1) / 2) * (3 + 5)
``````
The text passage primarily discusses an algorithm for converting postfix notation to infix notation, including examples and a Ruby implementation.
no_question

while the passage includes examples and explanations that could be considered as problem-solving, it does not explicitly pose a mathematical question that requires an answer. the content is more instructional and descriptive in nature.
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# Converting from postfix to infix

What would be a good algorithm for converting from postfix to infix? I've searched and searched but I only get algorithms for converting from infix to postfix. They're going to be decently similar algorithms correct? I also want to incorporate parenthesis. For example, (((13 - 1) / 2)(3 + 5)). Thank you!

• Maintain a stack 1. if you read a value push it to stack 2. if you read an operator, pop 2 values(say a,b) and push "(a operator b)" back to stack Seems like it will do – Sunny Agrawal Sep 27 '13 at 14:24

Here's the postfix version:-

``````13 1 - 2 / 3 5 + *
``````

To convert, parse it like an ordinary postfix parser, but store elements on the stack as a string, not as values:-

``````"13"
"1"
"-"
``````

when you get an operator, like above, convert to a single string and put parenthesis around it:-

``````"(13-1)"
``````

continuing:-

``````"(13-1)"
"2"
"/"
``````

becomes:-

``````"((13-1)/2)"
``````

continuing:-

``````"((13-1)/2)"
"3"
"5"
"+"
``````

becomes:-

``````"((13-1)/2)"
"(3+5)"
``````

finally:-

``````"((13-1)/2)"
"(3+5)"
"*"
``````

ends up as:-

``````"((13-1)/2)*(3+5)"
``````

you could treat "*" as a special case and omit it from the combined version.

We start with an empty stack. Assuming the postfix expression is correct :

• Read the atomic tokens and put them on stack
• when you reach an operator, pop n elements from the stack where n is the arity of the operator, format it correctly, put the brackets around it and push the resolution back to the stack
• when there's nothing to read, the stack should contain exactly one element with the result

For instance :

input : `2,3,+,5,-,8,*`

Stack contains after each step :

`````` 2
2,3
(2+3)
(2+3),5
((2+3)-5)
((2+3)-5),8
(((2+3)-5)*8)
``````

This would be my approach

``````while(input.hasNext()) {
if (symbol is operand) {
stack.push(symbol)
} else { // the symbol is an operator
if (stack.count < 2) {
ERROR too few operands
} else {
op2 = stack.pop();
op1 = stack.pop();
piece = "("+op1+symbol+op2+")";
stack.push(piece);
}
}
}

if (stack.count == 1) {
stack.pop() is the INFIX
} else {
ERROR
}
``````

Of course if you want to consider unary operators, the conditions have to be a little more structured to consider the stack with a single element

Here is a full Ruby implementation of the algorithm mentioned:

``````#!/usr/bin/env ruby

parts = gets.strip.split(/ +/)

stack = [ ]

parts.each do |part|
if part =~ /\D/  # it's a binary operation
right_operand = stack.pop
left_operand = stack.pop
stack.push("(#{left_operand} #{part} #{right_operand})")
else             # it's a number
stack.push(part)
end
end

if stack.size == 1
result = stack[0][1..-2]  # remove outer parentheses
puts result
exit(0)
else
puts "parse error, stack does not contain exactly one element"
exit(1)
end
``````

Use like this:

``````echo '13 1 - 2 / 3 5 + *' | ruby postfix-to-infix.rb
``````

This example produces the result:

``````((13 - 1) / 2) * (3 + 5)
``````
user
The text passage primarily discusses an algorithm for converting postfix notation to infix notation, including examples and a Ruby implementation.

TYPE: NO_QUESTION

While the passage includes examples and explanations that could be considered as problem-solving, it does not explicitly pose a mathematical question that requires an answer. The content is more instructional and descriptive in nature.