建表达式树并求值
#include <iostream> //一 p354
#include <string>
using namespace std;
const int maxn = 1010;
int lch[maxn], rch[maxn];
char op[maxn];
string S;
int nc = 0;
int build_tree(string &s, int x, int y) //返回值为该子树的根节点对应的下标
{
int c1 = -1, c2 = -1, p = 0;
int u;
if (y - x == 1)
{
u = ++nc;
lch[u] = rch[u] = 0;
op[u] = s[x];
return u;
}
for (int i = x; i < y; i++)
{
switch(s[i])
{
case '(': p++; break;
case ')': p--; break;
case '+': case '-': if (!p) c1 = i; break;
case '*': case '/': if (!p) c2 = i; break;
}
}
if (c1 == -1) c1 = c2;
if (c1 == -1) return build_tree(s, x + 1, y - 1);
u = ++nc;
lch[u] = build_tree(s, x, c1);
rch[u] = build_tree(s, c1 + 1, y);
op[u] = s[c1];
return u;
}
int dfs(int u) //计算
{
if (!lch[u] && !rch[u]) return op[u] - '0';
if (op[u] == '+') return dfs(lch[u]) + dfs(rch[u]);
else if (op[u] == '-') return dfs(lch[u]) - dfs(rch[u]);
else if (op[u] == '*') return dfs(lch[u]) * dfs(rch[u]);
else if (op[u] == '/') return dfs(lch[u]) / dfs(rch[u]);
}
int main(void)
{
cin >> S;
int l = S.size();
int root = build_tree(S, 0, l); //返回根节点
cout << dfs(root);
return 0;
}