Shunting-yard algorithm in c++
My suggestion is that you go straight to the relevant Wiki pages that describe
I have implemented the Shunting Yard algorithm in both Java and C++ and found the Wiki pages excellent and a great source of help. They are in sufficient detail so as to enable you to implement the algorithm step by step in whatever programming language you prefer.
Another suggestion: become reasonably familiar with the practical use of stacks and queues, as these are used all over the place in these algorithms.
Please see this blog posting for some C++ and Java implementations of the said Shunting Yard algorithm.
It also contains a further section (in progress) should you wish to include other mathematical operators (sin, cos, log etc) and more complicated expressions and sub-expressions.
user1311736
Updated on June 04, 2022Comments
-
user1311736 almost 2 years
I need a function that takes an infix string (like "3 + 4 * 9"), and convert it to postfix (like "4 9 * 3 +").
I got it working until you throw in parentheses within parentheses. I've been working on it all day and can't figure out what I'm doing wrong- can someone with a fresh mind see it, maybe? I feel like I'm really close!
Thanks! Here's the code:
string ExpressionManager::infixToPostfix(string infixExpression) { cout << "itop Testing : " << infixExpression << endl; string posnums = "0123456789"; string posops = "+-*/%(){}[]"; string onlyops = "+-/%*"; string space = " "; string openbra = "([{"; string closebra = ")]}"; stack <string> nums; stack <string> ops; string output = ""; //check to make sure expression is valid if (!(isBalanced(infixExpression))) { cout << "Infix Expression isn't balanced!" << endl; return "invalid"; } for (int i=0; i<infixExpression.size(); i++) { if ((posnums.find(infixExpression[i])!=string::npos) || (posops.find(infixExpression[i])!=string::npos) || (space.find(infixExpression[i])!=string::npos)) {} else { cout << "Invalid character " << infixExpression[i] << " found." << endl; return "invalid"; } } int numcount = 0; int opcount = 0; //Numbers vs. Operators for (int i = 0; i < infixExpression.size(); i++) { if (posnums.find(infixExpression[i]) != -1) { while(infixExpression[i] != ' ') { if (i == (infixExpression.size()-1)) break; i++; } numcount++; } if (onlyops.find(infixExpression[i]) != -1) { opcount++; } } if (opcount == (numcount - 1)) { } else { cout << "Bad operators to numbers ratio!" << endl; return "invalid"; } //Get rid of proceeding whitespaces. int safety = 0; int net = infixExpression.size(); while (infixExpression[0] == ' ') { infixExpression.erase(0,1); safety++; if (safety>=net) break; } //cout << "At this point, it is " << postfixExpression << endl; //the fun part! Set up stacks for (int i =0; i< infixExpression.size(); i++) { cout << "It gets hung up on character " << infixExpression[i] << endl; if(openbra.find(infixExpression[i]) != -1) { string word = ""; word += infixExpression[i]; ops.push(word); cout << "Pushing onto stack: " << word << endl; } else if(closebra.find(infixExpression[i]) != -1) { cout << "contents of remaining ops stack: "<< endl; stack <string> temp; temp = ops; for (int j = 0; j < temp.size(); j++) { cout << "\t" << temp.top() << endl; temp.pop(); } while (openbra.find(ops.top()) == -1) { output += " " + ops.top(); cout << "Pushing from stack: " << ops.top() << endl; ops.pop(); } cout << "Pushing from stack: " << ops.top() << endl; ops.pop(); } else if (posnums.find(infixExpression[i]) != -1) { string word = ""; while (infixExpression[i] != ' ') { word += infixExpression[i]; i++; if (i== infixExpression.size()) break; } output += " " + word; } else if (onlyops.find(infixExpression[i]) != -1) { if (ops.size() == 0) { string word = ""; word += infixExpression[i]; ops.push(word); } else { int o1p = 0; int o2p = 0; if ((infixExpression[i] == '+') || (infixExpression[i] == '-')) o1p = 0; else o1p = 1; if ((ops.top() == "+") || (ops.top() == "-")) o2p = 0; else o2p = 1; while ((ops.size() > 0) && (o1p <= o2p)) { output += " " + ops.top(); cout << "(odd) Pushing from stack: " << ops.top() << endl; if ((ops.top() == "+") || (ops.top() == "-")) o2p = 0; else o2p = 1; if (ops.size() > 0) { ops.pop(); } else { break; } } string word = ""; word += infixExpression[i]; ops.push(word); } } } while (output[0] == ' ') { output.erase(0,1); } return output; }