热心网友
回答时间:2024-10-24 06:03
#include <iostream>
#include <string>
#include <vector>
using namespace std;
const int N = 10000;
int lch[N], rch[N], res[N], top = 0;
char sym[N];
int toDigit(const string &str)
{
int ret; char tmp[50];
sprintf(tmp, "%s", str.c_str());
sscanf(tmp, "%d", &ret);
return ret;
}
bool issymbol(char c)
{
return c == '+' || c == '-' || c == '*' || c == '/' || c == '(' || c == ')';
}
vector<string> toStringArray(const string &str)
{
vector<string> vstr;
string pstr = ""; for(int i=0; i<str.length(); ++i) if(!isspace(str[i])) pstr += str[i];
string tmp = "";
for(int i=0; i<pstr.length(); ++i)
{
if(isdigit(pstr[i]))
{
tmp += pstr[i];
}
if(issymbol(pstr[i]))
{
vstr.push_back(tmp); tmp = pstr[i];
vstr.push_back(tmp); tmp = "";
}
}
vstr.push_back(tmp);
return vstr;
}
int build(const vector<string> &vstr, int x, int y)
{
if(y - x <= 1)
{
int k = top++;
lch[k] = rch[k] = -1;
res[k] = toDigit(vstr[x]); sym[k] = '#';
return k;
}
int flag = 0, sy1 = -1, sy2 = -1;
for(int i=x; i<y; ++i)
{
if(issymbol(vstr[i][0]))
{
switch(vstr[i][0])
{
case '(' : flag++; break;
case ')' : flag--; break;
case '+' : case '-' : if(!flag) sy1 = i; break;
case '*' : case '/' : if(!flag) sy2 = i; break;
}
}
}
if(sy1 >= 0 || sy2 >= 0)
{
#define loc (sy1 != -1 ? sy1 : sy2)
int k = top++;
lch[k] = build(vstr, x, loc - 1);
rch[k] = build(vstr, loc + 1, y);
res[k] = 0; sym[k] = vstr[loc][0];
return k;
}
else
{
return build(vstr, x + 1, y - 1);
}
}
int cul(int x)
{
if(sym[x] != '#')
{
int l = cul(lch[x]), r = cul(rch[x]);
switch(sym[x])
{
case '+' : res[x] = l + r; break;
case '-' : res[x] = l - r; break;
case '*' : res[x] = l * r; break;
case '/' : res[x] = l / r; break;
}
return res[x];
}
else
{
return res[x];
}
}
int main(int argc, char *argv[])
{
string str;
getline(cin ,str);
vector<string> vstr = toStringArray(str);
int root = build(vstr, 0, vstr.size());
cout << cul(root) << endl;
return 0;
}
收起