Answered step by step
Verified Expert Solution
Question
1 Approved Answer
HELP in error in program to convert infix to postfix in c++. I had to write a program that prints out postfix string from infix
HELP in error in program to convert infix to postfix in c++.
I had to write a program that prints out postfix string from infix string where operands and operators are separated by spaces. Eg - input > 2 + 3 output 2 3 +. Please point out error in my code in which I used shunting algorithm. Please do not provide completely new code but rather try to fix my own code.
#include#include #include #include #include using namespace std; //function to change string to postfix vector toPostfix(vector & tokens); //parse string vector parse(string input); // function to check operator's precedence bool GreaterPrecedence(string operator1, string operator2); // function to check whether a character is an operator. bool IsOperator(string str); //function for operator precedence int GetOperatorPrecedence(string opt); //function for equal precedence bool EqualPrecedence(string operator1, string operator2); // Function to verify operand bool IsOperand(string opd); //function to check left associativity bool IsLeftAssociative(string opt); //------------------------------------------------------------------------------------- int main() { cout << ">"; string input; cin >> input; vector output; vector tokens; cout << "before parse input" << endl; tokens = parse(input); cout << "after parse input" << endl; output = toPostfix(tokens); cout << "after postfix tokens" << endl; for (auto entry : output) //The auto keyword gets the type from the expression on the right of =. { cout << entry << " "; } } //parse string into necessary tokens by whitespaces. For example rt or a double digit number must be stored in a single token //The input is assumed to contain whitespaces after every operand and operator vector parse(string input) { vector tokens; //stores tokens that are obtained after getting rid of whitespaces string tmp; //declares a new stream variable str and initializes its buffer to a copy of input istringstream str(input); while (str >> tmp) { //push back the extracted word tokens.push_back(tmp); } return tokens; } vector toPostfix(vector & tokens) { //stack to temporarily store operators stack opStack; //vector to store postfix tokens vector postfix; //while there are tokens to be read for each token, for(int i = 0;i< sizeof(tokens);i++) { cout << tokens[i] << endl; cout << "first for loop " << endl; // Scanning each token from left. //if token is number push into output queue, in our case vector. if (IsOperand(tokens[i])) { cout << "first if loop " << endl; postfix.push_back(tokens[i]); } // if the token is an operator, then: if (IsOperator(tokens[i])) { cout << "isoperator if loop " << endl; //while there is an operator at the top of the operator stack with greater precedence //or the operator at the top of the operator stack has equal precedence and is left associative //and the operator at the top of the stack is not a left bracket while( (!opStack.empty() && GreaterPrecedence(opStack.top(), tokens[i])) || (EqualPrecedence(opStack.top(), tokens[i]) && IsLeftAssociative(opStack.top())) && opStack.top() != "(" ) { //pop operators from the stack, onto the output vector while(!opStack.empty()) { postfix.push_back(opStack.top()); opStack.pop(); } //push the read operator onto the operator stack postfix.push_back(tokens[i]); } } //if the token is a left bracket (i.e. "("), then: if(tokens[i] == "(") { //push it onto the operator stack. postfix.push_back(tokens[i]); } // if the token is a right bracket (i.e. ")"), then: if(tokens[i] == ")") { // while the operator at the top of the operator stack is not a left bracket: while(opStack.top() != "(") { // pop operators from the operator stack onto the output queue. postfix.push_back(opStack.top()); opStack.pop(); } // if the stack runs out without finding a left bracket, then there are //mismatched parentheses if(opStack.empty()) { cout << "Mismatched Paretheses" << endl; } else // pop the left bracket from the stack. opStack.pop(); } } //if there are no more tokens to read: //while there are still operator tokens on the stack: while(!opStack.empty()) { // if the operator token on the top of the stack is a bracket, then mismatched parentheses. if(opStack.top() == "(" || opStack.top() == ")") { cout << "mismatched parentheses" << endl; } // pop the operator onto the output queue. postfix.push_back(opStack.top()); opStack.pop(); } return postfix; } bool IsOperand(string Oprd) { cout << "inside isOperand method" << endl; if(Oprd == "+" || Oprd == "-" || Oprd == "*" || Oprd == "/"|| Oprd == "rt"|| Oprd == "^" ) return false; else return true; } bool IsOperator(string Oprt) { cout << "inside isOprt method" << endl; if(Oprt == "+" || Oprt == "-" || Oprt == "*" || Oprt == "/"|| Oprt == "rt"|| Oprt == "^" ) return true; else return false; } // function to check operator's precedence //operator1-stack operator2-token bool GreaterPrecedence(string operator1, string operator2) { if(GetOperatorPrecedence(operator1) > GetOperatorPrecedence(operator2)) { return true; } else return false; } bool EqualPrecedence(string operator1, string operator2) { if(GetOperatorPrecedence(operator1) == GetOperatorPrecedence(operator2)) { return true; } else return false; } // int GetOperatorPrecedence(string op) { if(op == "^" || op == "rt" ) { return 3; } if(op == "+" || op == "-" ) { return 2; } if(op == "*" || op == "/" ) { return 1; } } bool IsLeftAssociative(string opt) { if (opt == "^" || opt == "rt") { return false; } return true; }
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started