Apopular way to evaluate expressions is to transform them to postfixnotation to

Question

Apopular way to evaluate expressions is to transform them to postfixnotation to take care of the precedence rules, thencompute the output. Here is a sample input & output.

Input: A * (B +C)
Output: ABC+*

Which datastructure is typically used for this infix to postfixconversion?

Hash table

sorted array

queue

Apopular way to evaluate expressions is to transform them to postfixnotation to take care of the precedence rules, thencompute the output. Here is a sample input & output.

Input: A * (B +C)
Output: ABC+*

Which datastructure is typically used for this infix to postfixconversion?

Hash table

sorted array

queue

stack

Explanation / Answer

//Here is c++ program. #include <string.h> #include <vector> #include <stdlib.h> #include <stdio.h> #include <iostream> #include <math.h> #include <stack> using namespace std; char *remove_space(char *); void ValidateParenthesis (vector<string>); bool isOperand (string); bool isOperaopr_supported (string); int precedence (string); double evaluate (double, double, string); double evaluate (vector<string>); double StringToNum (string); vector<string> ConvertToPostfixExpression (vector<string>);
#include <string.h> #include <vector> #include <stdlib.h> #include <stdio.h> #include <iostream> #include <math.h> #include <stack> using namespace std; char *remove_space(char *); void ValidateParenthesis (vector<string>); bool isOperand (string); bool isOperaopr_supported (string); int precedence (string); double evaluate (double, double, string); double evaluate (vector<string>); double StringToNum (string); vector<string> ConvertToPostfixExpression (vector<string>);

int main (int argc, char* argv[]) { string s;int i,m,n,lo=0,count; char *ptr; vector<string>expression_infix; int len; string loop[4];


do { cout<<"Enter expression_infix:"; getline(cin,s);
}while(s.length()==0);
s = loop[count]; m=0;n=0; // cout<<s<<" is of len "<<s.length()<<endl; for(i=0;i<s.length();i++)   {   n++;   if(!isOperand(s.substr(i,1)))   {   if(lo ==0) {   //expression_infix.push_back(s.substr(m,n-1));   ptr = (char*)(s.substr(m,n-1)).c_str(); // fprintf(stdout,"ptr is %s.",ptr);   if(remove_space(ptr)!=NULL)   expression_infix.push_back(remove_space(ptr)); }   expression_infix.push_back(s.substr(i,1));   m=i+1;   n=0;   lo=1;   }else if(s.substr(i,1)!=" ") lo=0;   }   ptr = (char*)(s.substr(m,n)).c_str(); // fprintf(stdout,"ptr is %s.",ptr);   if(remove_space(ptr)!=NULL)   expression_infix.push_back(remove_space(ptr)); // expression_infix.push_back(s.substr(m,n)); /*for(i=0;i<expression_infix.size();i++) cout<<expression_infix[i]<<endl; */ vector<string> expression_postfix(ConvertToPostfixExpression(expression_infix)); cout << " Infix notation: "; for (int i = 0; i < expression_infix.size (); i++) cout << expression_infix[i] << " "; cout << " Postfix notation: "; for (int i = 0; i < expression_postfix.size (); i++) cout << expression_postfix[i] << " "; cout << " Result : "; cout << evaluate (expression_postfix) << " "; system ("pause"); return 0; } void ValidateParenthesis (vector<string> expression_infix) { int left = 0, right = 0; for (int i = 0; i < expression_infix.size(); i++) if (expression_infix[i] == "(") left++; else if (expression_infix[i] == ")") right++; if (left != right) { cout << "Error: Parenthesis do not match! "; system ("pause"); exit (1); } } double evaluate (double nd1, double nd2, string opr_supported) { if (opr_supported == "+") return nd1 + nd2; else if (opr_supported == "-") return nd1 - nd2; else if (opr_supported == "*") return nd1 * nd2; else if (opr_supported == "/") { if (nd2 == 0) { cout << "Evalutation error! "; system ("pause"); exit (1); } return nd1 / nd2; } else if (opr_supported == "%") { if (nd2 == 0) { cout << "Evaluation error! "; system ("pause"); exit (1); } return (double) ((int) nd1 % (int) nd2); } } double evaluate (vector<string> expression_postfix) { double nd1, nd2; stack<double> nd; for (int i = 0; i < expression_postfix.size (); i++) { if (isOperand (expression_postfix[i])) nd.push (StringToNum (expression_postfix[i])); else { nd2 = nd.top (); nd.pop (); nd1 = nd.top (); nd.pop (); nd.push (evaluate (nd1, nd2, expression_postfix[i])); } } return nd.top (); } bool isOperand (string nd) { if (nd == "(" || nd == ")" || nd == "+" || nd == "-" || nd == "*" || nd == "/" || nd == "%" ) return false; else return true; } bool isOperator (string opr_supported) { if (opr_supported == "+" || opr_supported == "-" || opr_supported == "*" || opr_supported == "/" || opr_supported == "%" ) return true; else return false; } int precedence (string token) { if (token == "(" || token == ")") return 0; else if (token == "+" || token == "-") return 1; else if (token == "*" || token == "/" || token == "%") return 2; } double StringToNum (string nd) { return (double) (atoi (nd.c_str ())); } vector<string> ConvertToPostfixExpression (vector<string> expression_infix) { stack<string> opr_supported; vector<string> expression_postfix; for (int i = 0; i < expression_infix.size (); i++) { if (isOperand (expression_infix[i])) expression_postfix.push_back (expression_infix[i]); else    if (expression_infix[i] == "(") opr_supported.push (expression_infix[i]); else    if (expression_infix[i] == ")") { while (opr_supported.empty () || opr_supported.top () != "(") { if (opr_supported.empty ()) { cout << "Invalid expression "; system ("pause"); exit (1); } expression_postfix.push_back (opr_supported.top ()); opr_supported.pop (); } opr_supported.pop (); } else if (isOperator (expression_infix[i])) { if(opr_supported.empty ()) opr_supported.push (expression_infix[i]); else { while (!opr_supported.empty () && precedence (opr_supported.top ()) >= precedence (expression
int main (int argc, char* argv[]) { string s;int i,m,n,lo=0,count; char *ptr; vector<string>expression_infix; int len; string loop[4];


do { cout<<"Enter expression_infix:"; getline(cin,s);
}while(s.length()==0);
s = loop[count]; m=0;n=0; // cout<<s<<" is of len "<<s.length()<<endl; for(i=0;i<s.length();i++)   {   n++;   if(!isOperand(s.substr(i,1)))   {   if(lo ==0) {   //expression_infix.push_back(s.substr(m,n-1));   ptr = (char*)(s.substr(m,n-1)).c_str(); // fprintf(stdout,"ptr is %s.",ptr);   if(remove_space(ptr)!=NULL)   expression_infix.push_back(remove_space(ptr)); }   expression_infix.push_back(s.substr(i,1));   m=i+1;   n=0;   lo=1;   }else if(s.substr(i,1)!=" ") lo=0;   }   ptr = (char*)(s.substr(m,n)).c_str(); // fprintf(stdout,"ptr is %s.",ptr);   if(remove_space(ptr)!=NULL)   expression_infix.push_back(remove_space(ptr)); // expression_infix.push_back(s.substr(m,n)); /*for(i=0;i<expression_infix.size();i++) cout<<expression_infix[i]<<endl; */ vector<string> expression_postfix(ConvertToPostfixExpression(expression_infix)); cout << " Infix notation: "; for (int i = 0; i < expression_infix.size (); i++) cout << expression_infix[i] << " "; cout << " Postfix notation: "; for (int i = 0; i < expression_postfix.size (); i++) cout << expression_postfix[i] << " "; cout << " Result : "; cout << evaluate (expression_postfix) << " "; system ("pause"); return 0; } void ValidateParenthesis (vector<string> expression_infix) { int left = 0, right = 0; for (int i = 0; i < expression_infix.size(); i++) if (expression_infix[i] == "(") left++; else if (expression_infix[i] == ")") right++; if (left != right) { cout << "Error: Parenthesis do not match! "; system ("pause"); exit (1); } } double evaluate (double nd1, double nd2, string opr_supported) { if (opr_supported == "+") return nd1 + nd2; else if (opr_supported == "-") return nd1 - nd2; else if (opr_supported == "*") return nd1 * nd2; else if (opr_supported == "/") { if (nd2 == 0) { cout << "Evalutation error! "; system ("pause"); exit (1); } return nd1 / nd2; } else if (opr_supported == "%") { if (nd2 == 0) { cout << "Evaluation error! "; system ("pause"); exit (1); } return (double) ((int) nd1 % (int) nd2); } } double evaluate (vector<string> expression_postfix) { double nd1, nd2; stack<double> nd; for (int i = 0; i < expression_postfix.size (); i++) { if (isOperand (expression_postfix[i])) nd.push (StringToNum (expression_postfix[i])); else { nd2 = nd.top (); nd.pop (); nd1 = nd.top (); nd.pop (); nd.push (evaluate (nd1, nd2, expression_postfix[i])); } } return nd.top (); } bool isOperand (string nd) { if (nd == "(" || nd == ")" || nd == "+" || nd == "-" || nd == "*" || nd == "/" || nd == "%" ) return false; else return true; } bool isOperator (string opr_supported) { if (opr_supported == "+" || opr_supported == "-" || opr_supported == "*" || opr_supported == "/" || opr_supported == "%" ) return true; else return false; } int precedence (string token) { if (token == "(" || token == ")") return 0; else if (token == "+" || token == "-") return 1; else if (token == "*" || token == "/" || token == "%") return 2; } double StringToNum (string nd) { return (double) (atoi (nd.c_str ())); } vector<string> ConvertToPostfixExpression (vector<string> expression_infix) { stack<string> opr_supported; vector<string> expression_postfix; for (int i = 0; i < expression_infix.size (); i++) { if (isOperand (expression_infix[i])) expression_postfix.push_back (expression_infix[i]); else    if (expression_infix[i] == "(") opr_supported.push (expression_infix[i]); else    if (expression_infix[i] == ")") { while (opr_supported.empty () || opr_supported.top () != "(") { if (opr_supported.empty ()) { cout << "Invalid expression "; system ("pause"); exit (1); } expression_postfix.push_back (opr_supported.top ()); opr_supported.pop (); } opr_supported.pop (); } else if (isOperator (expression_infix[i])) { if(opr_supported.empty ()) opr_supported.push (expression_infix[i]); else { while (!opr_supported.empty () && precedence (opr_supported.top ()) >= precedence (expression

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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