算法描述
接受一个中缀表达式，输出相应的后缀表达式。使用一个栈来存储运算符。
（1）初始化一个空的运算符栈。
（2）在没有到达重罪表达式的结尾以及没有错误发生时，执行以下步骤：
1、获取中缀表达式中的下一个输入标记（常数、变量、算术运算符、左括号、右括号）。
2、如果标记是：
一个左括号：将其压入栈中。
一个右括号：连续弹出并显示栈中的元素，直到遇到一个左括号，但是不要显示这个左括号（如果直到栈为空了还没有找到一个左括号，则是一个错误的中缀表达式）
一个运算符：如果栈为空，或者标记具有比栈顶元素更高的优先级，则将其亚茹栈中。
否则，弹出并显示栈顶的元素；接着继续比较标记和新的栈顶元素。
一个操作数：显示他。
（3）档达到中缀表达式的结尾时，弹出并显示栈中的元素直到栈为空。
#include <iostream> #include <string> #include <cassert> #include <cctype> #include <stack> using namespace std; string postfix(string exp) { char token; char topToken; stack<char> opStack; string postfixExp; const string BLANK = " "; for( int i =0; i < exp.length(); i++) { token = exp[i]; switch(token) { case ' ': break; case '(': opStack.push(token); break; case ')': for(;;) { assert(!opStack.empty()); topToken = opStack.top(); opStack.pop(); if(topToken == '(') break; postfixExp.append(BLANK + topToken); } break; case '+': case '-': case '*': case '/': case '%': for(;;) { if( opStack.empty() || opStack.top() == '(' || (token == '*' || token == '/' || token == '%') && (opStack.top() == '+' || opStack.top() == '-') ) { opStack.push(token); break; } else { topToken = opStack.top(); opStack.pop(); postfixExp.append(BLANK + topToken); } } break; default: //操作数 postfixExp.append(BLANK + token); for(;;) { if( !isalnum(exp[i+1]) ) break; //标识符结尾 i++; token = exp[i]; postfixExp.append(1,token); } } } //弹出栈中剩余的运算符 for(;;) { if (opStack.empty()) break; topToken = opStack.top(); opStack.pop(); if ( topToken != '(' ) { postfixExp.append(BLANK + topToken); } else { cout < " ***Error infix expression *** \n"; break; } } return postfixExp; } int main() { string infixExp; cout << "NOTE :Enter # for infix expression to stop.\n"; for(;;) { cout << " \nInfix expression? "; getline(cin,infixExp); if(infixExp == "#") break; cout << "Postfix expression is " << postfix(infixExp) << endl; } }