表达式求值¹

题目描述

见链接

解题思路

本题实质上是求一个仅含+*的中缀表达式。

可以把它转化成树来做。

按照+和*的优先级把他们分成左、右子树，再递归划分。

然后简化一下，可以用map来做。

$C++$代码如下

#include <bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f map<char, double> value_map; double tryCalc(char *str, int l, int r) { int pos = -1; int tempPri = 0; //代表表达式的基准权值 如果有( ) 那么括号内的权值也会相应的上升下降 int curPri = INF - 1; //扫描一遍找到最小权值的pos for (int i = l; i < r; i++) { int nowPri = INF; switch (str[i]) { case '+': nowPri = tempPri + 1; break; case '*': nowPri = tempPri + 2; break; } if (curPri >= nowPri) { pos = i; curPri = nowPri; } } //递归计算表达式 //是个数字 if (pos == -1) { for (int i = l; i < r; i++) { if (str[i] < 'a' || str[i] > 'z') continue; if (value_map.find(str[i]) == value_map.end()) { char msg[100]; sprintf(msg, "There is no var named = %c", str[i]); throw runtime_error(msg); } return value_map[str[i]]; } //去掉前导的空格 while (l <= r && (str[l] > '9' || str[l] < '0')) l++; //将 tr里的l到r转换为数字 double num = atof(str + l); return num; } //递归计算权值最小的操作符的左子树和右子树的值 else { double a = tryCalc(str, l, pos); double b = tryCalc(str, pos + 1, r); switch (str[pos]) { case '+': return a + b; case '-': return a - b; case '*': return a * b; case '/': return a / b; case '^': return pow(a, b); } } } int main() { char str[1000]; scanf("%[^\n]s", str); getchar(); //printf("%lf\n", calc(str, 0, strlen(str))); cout << int(tryCalc(str, 0, strlen(str))) % 10000; return 0; }

---

2013年NOIP普及组第2题 ↩︎