// 后綴表達式轉中綴表達式，同時求值，O(n)// 數值棧 vector<int> nums; // 運算符棧 vector<char> ops;// 優先級 int grade(char op) {switch (op) {case '(':return 1;case '+':case '-':return 2;case '*':case '/':return 3;}return 0; }// 處理后綴表達式中的一個運算符 void calc(char op) {// 從棧頂取出兩個數 int y = *nums.rbegin();nums.pop_back();int x = *nums.rbegin();nums.pop_back();int z;switch (op) {case '+':z = x + y;break;case '-':z = x - y;break;case '*':z = x * y;break;case '/':z = x / y;break;}// 把運算結果放回棧中 nums.push_back(z); }// 中綴表達式轉后綴表達式，同時對后綴表達式求值 int solve(string s) {nums.clear();ops.clear();int top = 0, val = 0;for (int i = 0; i < s.size(); i++) {// 中綴表達式的一個數字 if (s[i] >= '0' && s[i] <= '9') {val = val * 10 + s[i] - '0';if (s[i+1] >= '0' && s[i+1] <= '9') continue;// 后綴表達式的一個數，直接入棧 nums.push_back(val);val = 0;}// 中綴表達式的左括號 else if (s[i] == '(') ops.push_back(s[i]);// 中綴表達式的右括號 else if (s[i] == ')') {while (*ops.rbegin() != '(') {// 處理后綴表達式的一個運算符 calc(*ops.rbegin());ops.pop_back();}ops.pop_back();}// 中綴表達式的加減乘除號 else {while (ops.size() && grade(*ops.rbegin()) >= grade(s[i])) {calc(*ops.rbegin());ops.pop_back();}ops.push_back(s[i]);} }while (ops.size()) {calc(*ops.rbegin());ops.pop_back();}// 后綴表達式棧中最后剩下的數就是答案 return *nums.begin(); }

總結

以上是生活随笔為你收集整理的信息竞赛进阶指南--中缀表达式转后缀表达式并求值（模板）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。