Program must be written in C++: Write a program that converts a fully parenthesi
ID: 3691234 • Letter: P
Question
Program must be written in C++:
Write a program that converts a fully parenthesized mathematical infix expression into an equivalent postfix expression and then evaluates the post-fix expression. A fully parenthesized expression is one in which parentheses surround every operator and its operands. Starting with an empty stack of strings to store operators and an empty queue of strings to store the postfix expression, the conversion can be implemented with the following rules: If ‘(‘ is input, then ignore it. If a number is input, then add it to the queue. If an operator (either ‘*’, ‘+’, ‘-’, or ‘/’) is input, then push it on the stack. If ‘)’ is input, then pop the operator from the stack and add it to the queue. If ‘q’ is input, then exit.
When the final operator is popped from the stack, the queue contains the equivalent postfix expression. Use your solution from Programming Project 10 to evaluate it. You will need to convert a string object to an integer. Use the c_str() function to convert the string to a C string, and then use the atoi function to convert the C string into an integer. Refer to Chapter 8 for details.
Sample output is shown below for ((10 - (2 + 3)) * 2), which translates to the postfix expression 10 2 3 + - 2 * :
(
(
10
-
(
2
+
3
)
)
*
2
)
q
The expression evaluates to 10
Explanation / Answer
#include #include #include #define size 20 class Infix { public: char stack[size],postfix[size]; int top; void push(char); int pop(); int priority(char); void inpost(char []); void posteval(); }; void Infix::push(char token) { if(top==size-1) cout<<"over flows"; else { top=top+1; stack[top]=token; } } int Infix::pop() { char token; if(top!=-1) { token=stack[top]; top=top-1; return(token); } return 0; } int Infix::priority(char token) { if(token=='^') return 3; else if(token=='/'||token=='*') return 2; else if(token=='+'||token=='-') return 1; else return 0; } void Infix::inpost(char infix[]) { char x; int i=0,j=0; char token,k; stack[++top]='$'; token=infix[i]; while(token!='') { if(token=='(') push(token); else if(token>='a'&&token<='z') postfix[j++]=token; else if(token=='^'||token=='/'||token=='*'||token=='+'||token=='/'||token=='-') { if(top==-1||stack[top]=='(') push(token); else if(priority(token)<=priority(stack[top])) { x=pop(); while(priority(token)<=priority(x)) { postfix[j++]=x; x=pop(); } push(x); push(token); } else if(priority(token)>priority(stack[top])) { push(token); } } else if(token==')') { x=pop(); while(x!='(') { postfix[j++]=x; x=pop(); } } token=infix[++i]; } while(stack[top]!='$') postfix[j++]=pop(); postfix[j]=''; cout<<"postfix expression is"<=65&&postfix[i]<=90)||(postfix[i]>=97&&postfix[i]<=122)) { cin>>n; push(n); } else { switch(postfix[i]) { case '+': op2=pop(); op1=pop(); push(op1+op2); break; case '-': op2=pop(); op1=pop(); push(op1-op2); break; case '*': op2=pop(); op1=pop(); push(op1*op2); break; case '/': op2=pop(); op1=pop(); push(op1/op2); break; case '$': op2=pop(); op1=pop(); push(pow(op1,op2)); break; default: cout<<" invalid choice..."; break; } } } cout<<" result = "<>infix; I.inpost(infix); cout<<" Infix expression is "; for(i=0;infix[i]!='';i++) cout<
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.