中綴表達式求值的兩種方法

左手的ㄟ右手 2023-08-17 17:47 103阅读 0赞

//遞歸法求中綴表達式的值 int calc(int l,int r) { for(int i=r,j=0;i>=l;--i) { if(s[i]=='(') ++j; if(s[i]==')') --j; if(j=='0'&&s[i]=='+') return calc(l,i-1)+calc(i+1,r); if(j=='0'&&s[i]=='-') return calc(l,i-1)-calc(i+1,r); } for (int i = r, j = 0; i >= l; i--) { if (s[i] == '(') j++; if (s[i] == ')') j--; if (j == 0 && s[i] == '*') return calc(l, i - 1) * calc(i + 1, r); if (j == 0 && s[i] == '/') return calc(l, i - 1) / calc(i + 1, r); } if(s[l]=='('&&s[r]==')') return calc(l+1,r-1); int ans=0; for (int i = l; i <= r; i++) ans = ans * 10 + s[i] - '0'; return ans; } //中綴表達式轉後綴表達式，同時求值 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(); } //歸納為三個原則：1、括號內的先計算 2、無括號情況下，優先級高的先計算，優先級低的後計算 3、優先級相同時，如何計算都可以。

转载于:https://www.cnblogs.com/tztqwq/p/11347674.html