转自：前，中，后缀表达式 前缀表达式，中缀表达式，后缀表达式都是四则运算的表达方式，用以四则运算表达式求值，即数学表达式的求值。比如一个简单的数学表达式 (1+2)-(3+4) 这是我们常见的数学表达式类型 即中缀表达式
把这个表达式转化位前缀表达式（也称波兰式） -+12+34把这个表达式转化位后缀表达式（也称逆波兰式） 12+34±为什么要将简单的中缀表达式转化为复杂的波兰式或逆波兰式 原因在于，简单的中缀表达式在用人的思维逻辑来看，确实简单，但在计算机看来中序表达式是非常复杂的结构，而相对而言，（逆）波兰式在计算机看来是非常简单的结构，因为计算机普遍采用的内存结构是栈式结构，而（逆）波兰表达式在其存储和计算上也采用的是栈的特性。 中缀表达式与后缀表达式的转换 1.建立一个栈，一个队列 2.从左至右顺序遍历中缀表达式。 3.遇到操作数时，直接压入队列 4.遇到运算符时： 当遇到左括号或是栈为空，直接压栈 当遇到右括号时，依次弹栈，直至栈顶是左括号，弹栈结束！期间所有的操作符按顺序入队 当遇到操作符时，若栈顶是左括号，则直接入栈 若栈顶是操作符，则比较两操作符优先级，若当前字符优先级较高，则压栈，若当前字 符优先级小于等于栈顶运算符，则将栈顶运算符弹出并入队，继续与当前栈顶元素比较！ 直到当前运算符优先级高于栈顶运算符则入栈，或是遇到左括号或是栈为空，亦入栈！ 5.遍历完所有字符后，弹出栈中仍剩有的操作符，并入队 6.依次出队即可达到相应的后缀表达式！
vector<string> mid2last(string str) { //简易版 中缀表达式转后缀，操作符只涉及+ - queue<string> q; stack<string> s; int n=str.size(); int start=-1; for(int i=0;i<n;++i) { //记录操作数的首位 if(str[i]>='0' && str[i]<='9') { if(start==-1) start=i; } else { if(start!=-1) { //将完整操作数入队 q.push(string(str.begin()+start,str.begin()+i)); //cout<<string(str.begin()+start,str.begin()+i); start=-1; } //遇到空格则继续遍历 if(str[i]==' ') continue; //作括号直接入栈 else if(str[i]=='(') s.push("("); else if(str[i]==')') { //右括号依次弹栈并入队，直至遇到左括号 string tmp=s.top(); s.pop(); while(tmp!="(") { q.push(tmp); tmp=s.top(); s.pop(); } } else if(str[i]=='+') { //遇到+号操作符，栈为空则直接进栈 if(s.empty()) s.push("+"); else { string tmp=s.top(); //栈顶为左括号亦直接进栈 if(tmp=="(") s.push("+"); //由于操作符只有+ -，且优先级一样，那么遇到栈中不可能共存多个操作符 //因此栈顶为操作符时，直接弹栈并入队，然后将当前字符入栈 else if(tmp=="+" || tmp=="-") { s.pop(); s.push("+"); q.push(tmp); } } } else if(str[i]=='-') { //遇到-号，同+号 if(s.empty()) s.push("-"); else { string tmp=s.top(); if(tmp=="(") s.push("-"); else if(tmp=="+" || tmp=="-") { s.pop(); s.push("-"); q.push(tmp); } } } } } if(start!=-1) { //末尾可能还有操作数，将操作数入队 q.push(string(str.begin()+start,str.end())); } while(!s.empty()) { //弹出栈中剩余操作符入队 q.push(s.top()); s.pop(); } vector<string> res; while(!q.empty()) { //以一定的格式保存后缀表达式 res.push_back(q.front()); q.pop(); } return res; }后缀表达式值的计算 1.建立一个栈 2.从左到右顺序遍历后缀表达式 3.遇到操作数则直接进栈 4.遇到操作符，则依次弹出栈顶上的两个元素，对其进行运算，然后将运算结果进栈 5.重复 2，3，直至遍历完整个表达式，那么栈中将只剩下一个元素，它就是整个表达式的运算结果
int evalRPN(vector<string>& tokens) { if(tokens.empty()) return 0; stack<int> helper; int n=tokens.size(); for(int i=0;i<n;++i) { int num; //运用c++字符串流，将字符串转化为整数 istringstream in(tokens[i]); in>>num; if(!in.fail()) { //若当前字符串是操作数，则转化成功，将操作数入栈 helper.push(num); } else { //若当前字符串是操作符，则转化失败 //依次弹出两个栈顶元素 int num1=helper.top(); helper.pop();; int num2=helper.top(); helper.pop(); //判断操作符种类，进行数学运算并将运算结果入栈 if(tokens[i]=="+") helper.push(num2+num1); else if(tokens[i]=="-") helper.push(num2-num1); else if(tokens[i]=="*") helper.push(num2*num1); else if(tokens[i]=="/") helper.push(num2/num1); } } return helper.top(); }前缀表达式在操作上与后缀表达式的几个不同点
前缀表达式的所有遍历从右到左的！自然遇到括号的处理方式与后缀表达式是相反的在与中缀表达式的转化时，遇到操作符的处理方式是，与栈顶元素比较，若优先级大于等于栈顶运算符，就直接入栈，注意在后缀表达式中是大于。