DS18 Alice做算术（3）

DS18 Alice做算术（3）

memory limit: 65536KB time limit: 1000MS

accept: 3 submit: 6

Description

对于单个的算术运算，Alice都已经掌握得很好了。爸爸开始出一些混合运算的题目给Alice做。每做完10道题目，就可以吃一个香蕉船。现在，Alice不但会求余运算，也学会了负数，因此，无论运算的中间结果和最终结果是负数，她都会做。
一般来说，一天下来，Alice都做不完10题。为什么呢？因为爸爸使坏了：虽然这些式子的每个运算都很简单，只有四则运算以及括号，但有些式子很长，有近万个运算数。有时Alice一条式子还没做完，就已经累得睡着了。

Input

有多行，每行代表一个算式。每行不超过10000个字符。式子中不含空格。

Output

对每行输入，输出一行结果。

对于非法运算，输出 illegal operation

Sample Input

1+2*10-10/2=

6/(5+1)=

1+1*3=

4/2*8=

10-5/2=

3*2/1=

12*5+3-10/5=

1/0=

Sample Output

16

1

4

16

8

6

61

illegal operation

Author

John

思路

做的时候发现ZQU的测试数据表达式居然包含空格,另外测试数据也不包含‘-(2+3)’，‘-(-3)’之类的数据，似乎有点弱。

下面给出我的代码，不过以下代码可以处理上面比较特别的数据，但需保证表达式绝对不含空格。

PS:如果包含空格的话，请自行在代码中多加一行除去空格即可。

#include <iostream>
#include <stack>
using namespace std;
const int maxn = 10010;
bool error; // 表达式是否存在错误
stack <int> istack; // 存放操作数
stack <char> cstack; // 存放操作符
stack <int> fstack; // 存放‘(’前的正负号
bool preop; // 前一个符号是否是操作符
bool prenum; // 前一个符号是否是操作数
int flag, num; // 正负号，及数字大小
void Init()
{
 while (!istack.empty()) istack.pop();
 while (!cstack.empty()) cstack.pop();
 while (!fstack.empty()) fstack.pop();
 preop = true;
 prenum = false;
 error = false;
 num = 0;
 flag = 1;
}
void Get(int &a)
{
 if (!istack.empty())
 {
  a = istack.top();
  istack.pop();
 }
 else error = true;
}
void Add()
{
 int a, b;
 Get(a);
 Get(b);
 if (!error) istack.push(b+a);
}
void Sub()
{
 int a, b;
 Get(a);
 Get(b);
 if (!error) istack.push(b-a);
}
void Mul()
{
 int a, b;
 Get(a);
 Get(b);
 if (!error) istack.push(b*a);
}
void Div()
{
 int a, b;
 Get(a);
 Get(b);
 if (!a) error = true;
 if (!error) istack.push(b/a);
}
void GetOp(char &op)
{
 if (!cstack.empty())
 {
  op = cstack.top();
  cstack.pop();
 }
 else error = true;
}
void play(char s[])
{
 char op;
 while (*s && !error)
 {
  if (*s>='0' && *s<='9')
  {
   num *= 10; num += *s - '0';
   prenum = true;
   preop = false;
  }
  else
  {
   if (prenum && *s!='(')
   {
    istack.push(flag*num);
    flag = 1; // 重新赋值为正号
    num = 0;
    if (!cstack.empty())
    {
     GetOp(op);
     // 先做乘除运算
     if (op == '*') Mul();
     else if (op == '/') Div();
     else cstack.push(op); // 其他符号放回去暂不处理
    }
   }
   if (*s == '(') // 特殊处理，为了处理类似“-(9+3)=”，“-(-5)=”之类的表达式
   {
    fstack.push(flag); // 保存括号前的符号
    flag = 1;
    num = 0;
   }
   if (*s=='-' && preop) // 表示当前是负号而不是减号
   {
    flag = -flag;
   }
   else
   {
    if (*s == ')') // 先将括号内的部分全部计算完成
    {
     while (!cstack.empty())
     {
      GetOp(op);
      if (op == '*') Mul();
      else if (op == '/') Div();
      else if (op == '+') Add();
      else if (op == '-') Sub();
      else if (op == '(') break;
     }
     if (op != '(') // 括号不匹配
     {
      error = false;
      return;
     }
     if (!istack.empty())
     {
      int top = istack.top(); istack.pop();
      if (fstack.empty()) // 括号不匹配使可能出现，不过程序那时走不到这句
      {
       error = true;
       return;
      }
      int ft = fstack.top(); fstack.pop();
      istack.push(top*ft); // 与括号前的符号一起计算括号内的值
     }
     while (!cstack.empty()) // 把括号前面与括号相连的乘除一并计算
     {
      GetOp(op);
      if (op == '*') Mul();
      else if (op == '/') Div();
      else 
      {
       cstack.push(op);
       break;
      }
     }
    }
    else cstack.push(*s); // 除‘)’外的操作符全部进栈
   }
   prenum = false; // 当前符号不是操作数
   preop = true; // 当前符号是操作符
  }
  s++;
 }
 // ‘=’出栈
 if (!cstack.empty() && cstack.top()=='=') cstack.pop();
 while (!error && !cstack.empty())
 {
  GetOp(op);
  if (op == '*') Mul();
  else if (op == '/') Div();
  else if (op == '+') Add();
  else if (op == '-') Sub();
  else error = false; // 若表达式存在错误操作符
 }
 if (istack.size() != 1) error = true; // 非正常计算
}
int main()
{
 char exp[maxn];
 while (gets(exp))
 {
  Init();
  play(exp);
  if (!error) printf("%d\n",istack.top());
  else printf("illegal operation\n");
 }
 return 0;
}