Write a program in c++ that takes an infix expression from user through command

Question

Write a program in c++ that takes an infix expression from user through command line argument and convert it into a postfix expression. You are required to use the stack data structure for the implementation of this task.

Explanation / Answer

Consider an infix string x+y*c.Each character of the string is called tokens. The algorithm for converting an infix expression to postfix expression is given below. We need a stack to solve this problem Algorithm for converting infix expression to postfix expression: Initialize an empty stack and a Postfix String S. Read the tokens from the infix string one at a time from left to right If the token is an operand, add it to the Postfix string S. If the token is a left parentheses, Push it on to the stack If the token is a right parentheses Repeatedly Pop the stack and add the poped out element in to the string S until a left parenthesis is encountered; Remove the left parenthesis from the stack and ignore it If the token is an operator If the stack is empty push the operator in to the stack If the stack is not empty compare the precedence of the operator with the element on top of the stack If the operator in the stack has higher precedence than the token Pop the stack and add the poped out element in to the string S. else Push the operator in to the stack Repeat this step until the stack is not empty or the operator in the stack has higher precedence than the token Repeat this step till all the characters are read. After all the characters are read and the stack is not empty then Pop the stack and add the tokens to the string S Return the Postfix string S Example for Converting infix to Postfix Expression: Example 1: Infix String----->A*B+C/D Solution: Initially the stack is empty and the Postfix String S has no characters Read the token A.A is a operand so it is added to the string S.now Stack->empty and S->A Read the token *.* is an operator.stack is empty so push * in to the stack. now Stack->* and S->A Read the token B.B is an operand so it is added to the string S. now Stack->* and S->AB Read the token +.+is an operator.compare +and *.* has higher precedence than +. so pop * from the stack and add it to the string S. now Stack->empty and S->AB*.now the stack is empty so push the + in to the stack.now Stack->+ and S->AB* Read the token C.C is a operand so it is added to the string S.now Stack->+ and S->AB*C Read the token /./ is an operator.compare /and +./ has higher precedence than +. so push / in to the stack . now Stack->+/ and S->AB*C Read the token D.D is a operand so it is added to the string S.now Stack->+/ and S->AB*CD All the characters are read but the stack is not empty so pop the stack and add the characters to the String. now S->AB*CD/+ So the Postfix String is AB*CD/+ Source(s): http://datastructuresprogramming.blogspot.com/2010/02/evaluating-postfix-expression.html

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.