本文共 3860 字，大约阅读时间需要 12 分钟。

中缀表达式转后缀表达式思路:

    首先给用到的每个操作符如'+', '-', '*', '/'等按照他们原本的计算优先级定义两个代表优先级的数值， 如inStackPri代表入栈之后的优先级， outStackPri代表入栈之前的优先级...

    然后扫描表达式， 如果是数字， 直接输出， 如果是')', 则将栈顶操作符依次出栈， 直到遇到'('...如果是其他操作符， 则用这个操作符的outStackPri值和栈顶的操作符的inStackPri进行比较， 如果小于， 则将栈顶的操作符出栈并输出， 之后再次将outStackPri和栈顶操作符的inStackPri比较，如果仍小于， 继续出栈， 直到outStackPri大于栈顶操作符的inStackPri, 然后将当前这个操作符入栈...当扫描完表达式时， 如果栈中还有操作符， 则依次出栈输出...最后输出的就是后缀表达式...

后缀表达式计算思路：

    一次扫描后缀表达式， 如果是数字， 则压栈， 如果是操作符， 则依次取出栈顶的两个操作数进行计算， 并将计算结果压栈， 当扫描完表达式时， 栈中的元素就是表达式的计算结果...

    具体的实现如下(这个实现没有考虑对错误的处理， 假定输入的表达式是正确的， 且操作符都是二元操作符)

#include <cstdlib>#include <iostream>#include <map>#include <vector>#include <string>#include <stack>#include <cmath>using namespace std;const int OPERA_COUNT = 8;map<char, int> inStackPri;map<char, int> outStackPri;char opera[] = {'#', '(', '^', '*', '/', '+', '-', ')'};int priority[][2] = {​{0, 0}, {1, 8}, {7, 6}, {5, 4}, {5, 4}, {3, 2}, {3, 2}, {8, 1}};void initMap(){ for(int i=0; i< OPERA_COUNT; i++) { inStackPri.insert(make_pair(opera[i], priority[i][0])); outStackPri.insert(make_pair(opera[i], priority[i][1])); }}string createSufixExp(const string &expre){ string sufixExp; stack<char> opera; opera.push('#'); int expSize = expre.size(); int i = 0; while(i < expSize) { char ch = expre[i]; if(isdigit(ch)) sufixExp += ch; else { char topC = opera.top(); if(ch == ')') { while(topC != '(') { sufixExp += topC; opera.pop(); topC = opera.top(); } opera.pop(); } else { while((inStackPri[topC]) > (outStackPri[ch])) { sufixExp += topC; opera.pop(); topC = opera.top(); } opera.push(ch); } } i++; } while(!opera.empty()) { if(opera.top() != '#') sufixExp += opera.top(); opera.pop(); } return sufixExp; }int calResult(char ch, int opa1, int opa2){ int result = 0; switch(ch) { case '+': result = opa1 + opa2; break; case '-': result = opa1 - opa2; break; case '*': result = opa1 * opa2; break; case '/': result = opa1 / opa2; break; case '^': result = pow((double)opa1, (double)opa2); break; default: break; } return result;}int getResult(const string &exp){ int result = 0; int expSize = exp.size(); int i = 0; stack<int> opa; while(i < expSize) { char ch = exp[i]; if(isdigit(ch)) opa.push(atoi(&ch)); else { int opa1 = opa.top(); opa.pop(); int opa2 = opa.top(); opa.pop(); result = calResult(ch, opa2, opa1); opa.push(result); } i++; } return opa.top();}int main(int argc, char *argv[]){ initMap(); freopen("input.txt", "rt", stdin); freopen("output.txt", "wt", stdout); string expression; while(getline(cin, expression)) { string sufixExp = createSufixExp(expression); cout << "sufix expression is: " << sufixExp << endl; int result = getResult(sufixExp); cout << "result is: " << result << endl; } return EXIT_SUCCESS;} 

测试输入：

1+2*(3-4)-9/3

3*2+(9-0)^2

1+9+5

输出：

sufix expression is: 1234-*+93/-

result is: -4

sufix expression is: 32*90-2^+

result is: 87

sufix expression is: 19+5+

result is: 15

参考：《数据结构》殷人昆

转载地址：http://qfkqb.baihongyu.com/