CODEWITHSUNDEEP
algorithmdata-structuresstackprefixinfix-notation
Milad
Milad

Reputation: 77

How To Insert Parenthesis In An Infix Expression Using Stack

I need an algorithm to insert parenthesis in an infix expression using stack. for example:

input : 12/c+c*p^(8+9)

output : ((12/c)+(c*(p^(8+9))))

I just need the algorithm for this and it is ok if we reach the output through prefix or postfix. but the output should be exact as the example. an infix expression with full parenthesis.

I'll appreciate if someone can give a pseudocode or step by step example.

Thanks

Upvotes: 0

Views: 2818

Answers (2)

amir_70
amir_70

Reputation: 930

1 - convert to postfix

2 - read the postfix expression

3 - a loop on postfix expression ... if character is operand push in stack else if operator ... pop top two in the stack and insert this two with the operator that is current character in the parentheses and push it in stack again

Upvotes: 0

Bill
Bill

Reputation: 488

I have achieved this before by means of reverse polish notation (RPN). First you need to construct a postfix version of the expression. You could use the shunting-yard algorithm. Secondly, you need to "evaluate" (symbolically) the postfix expression you just created. The RPN evaluation algorithm does this.

Upvotes: 2

Related Questions