this program takes infix algebraic notations and converts them to prefix notations....i get too many operators though....
2-3+4 ends up looking lik
--+234 //notice the extra - ...but not +
if anyone's got some serious time to kill, could you look over this for me? you should be able to cut, paste, compile, run....at system prompt just type in different equations to see the output...type 'exit' to quit...oh yea, i forgot to include 'support' for exponents (2^3)
btw.........i know stack<char> is not what i really want to use (the char part anyway), but it keeps this logical testing a little easier)
Code:#include <iostream> #include <string> #include <stack> using namespace std; //i love macros #define isOp(x) (x=='-'||x=='+'||x=='/'||x=='*') #define isHigh(x) (x=='*'||x=='/') #define isLow(x) (x=='-'||x=='+') #define isSame(x, y) ((isHigh(x) && isHigh(y)) ||(isLow(x) && isLow(y))) #define isClose(x) ((x==']')||(x==')')||(x=='}')) #define isOpen(x) ((x=='[')||(x=='(')||(x=='{')) string reverse(string s) { string tar; for(int i = s.size(); i >= 0; i--) { tar += s[i]; } return tar; } string infix2prefix(string source) { stack<char> output; stack<char> ops; string eq(reverse(source)); //reverse equation char c; //for each element in equation for(int i = 0; i < eq.size(); i++) { c = eq[i]; //prevent repeated dereferencing //if not /-+*[]{}() if((!isOp(c))&&(!isClose(c))&&(!isOpen(c))) output.push(c); //if is )}] if(isClose(c)) ops.push(c); //if is /+-*^ if(isOp(c)) { //if stack is empty put operator on stack if(ops.empty()) { ops.push(c); }else{ //else if top of stack is )]or} push operator on stack if(isClose(ops.top())) { ops.push(c); } //is precedence is the same or higher push it onto //operator stack...else, push it straight to output //stack if(isSame(c, ops.top())||isHigh(c)) { ops.push(c); }else{ output.push(c); } } } //if ([or{ if(isOpen(c)) { //move operator stack to output stack while(!ops.empty()) { output.push(ops.top()); ops.pop(); } } } //put remaining operators on output stack while(!ops.empty()) { output.push(ops.top()); ops.pop(); } //turn output stack into a string eq = ""; while(!output.empty()) { eq += output.top(); output.pop(); } return eq; } int main() { string eq; char c; cin >> eq; while(eq != "exit") { cout << infix2prefix(eq) << endl; cin >> eq; } return 0; }