本文的主要內容是如何求一個給定的表達式的值，具體思路就是先將普通算術的中綴表達式轉化為后綴表達式，這一步用到的算法叫做調度場算法。然后對后綴表達式，也就是逆波蘭表達式求值。

題目：http://acm.hdu.edu.cn/showproblem.php?pid=3596

代碼：（參考別人的重構）

#include <iostream> #include <string.h> #include <stdio.h> #include <math.h> #include <stack> #include <map>#define N 10005 #define EPS 1e-9 using namespace std;struct Node {double val;char opt;Node(double val = 0, char opt = ' '){this->val = val;this->opt = opt;} };Node node[N]; char str[N]; map<char, int> mp;void Init() {mp['('] = 0;mp['-'] = mp['+'] = 1;mp['*'] = mp['/'] = 2;mp['^'] = 3; }//逆波蘭表達式的計算 double CalPoland(Node node[], int n) {stack<double> s;for(int i = 0; i < n; i++){if(node[i].opt == ' ')s.push(node[i].val);else{double a = s.top();s.pop();double b = s.top();s.pop();switch(node[i].opt){case '+':s.push(b + a);break;case '-':s.push(b - a);break;case '*':s.push(b * a);break;case '/':if(fabs(a) < EPS)throw true;s.push(b / a);break;case '^':s.push(pow(b, a));break;}}}return s.top(); }//調度場算法 double ShuntYardAlgo(char str[]) {stack<char> oper;//inNum標記當前是否可以輸入數字bool inNum = true;//hasDot標記是否已經輸入小數點bool hasDot = true;int p = 0; //掃描指針位置int cnt = 0; //符號或者數字計數器int sign = 1; //表示正負符號while(str[p]){if(isdigit(str[p]) || str[p] == '.'){if(inNum){double val = 0;double w = 1;if(str[p] == '.'){hasDot = true;val = 0;}else{hasDot = false;val = str[p] - '0';}p++;while(isdigit(str[p]) || str[p] == '.'){if(str[p] == '.'){if(hasDot) throw true;hasDot = true;}else{if(hasDot){w *= 0.1;val += (str[p] - '0') * w;}elseval = val * 10 + str[p] - '0';}p++;}p--;node[cnt++] = Node(val * sign, ' ');sign = 1;inNum = false;}else throw true;}else{switch(str[p]){case '(':oper.push(str[p]);break;case ')':while(!oper.empty() && oper.top() != '('){node[cnt++] = Node(0, oper.top());oper.pop();}if(oper.empty())throw true;oper.pop();break;case '+':case '-':case '*':case '/':case '^':if(inNum){if(str[p] != '+' && str[p] != '-') throw true;while(str[p] == '+' || str[p] == '-'){if(str[p] == '-') sign *= -1;p++;}p--;}else{while(!oper.empty() && mp[str[p]] <= mp[oper.top()]){node[cnt++] = Node(0, oper.top());oper.pop();}oper.push(str[p]);inNum = true;}break;}}p++;}while(!oper.empty()){node[cnt++] = Node(0, oper.top());oper.pop();}return CalPoland(node, cnt); }int main() {Init();while(scanf("%s", str) != EOF){try{printf("%.8lf\n", ShuntYardAlgo(str));}catch(bool){puts("The teacher is so lazy!");}}return 0; }

總結

以上是生活随笔為你收集整理的调度场算法与逆波兰表达式的全部內容，希望文章能夠幫你解決所遇到的問題。

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