数学表达式求值-蒲公英云

成绩	10	开启时间	2017年10月18日星期三 17:40
折扣	0.8	折扣时间	2017年11月8日星期三 23:55
允许迟交	否	关闭时间	2018年01月8日星期一 23:55

问题描述

　　带有变量的中缀表达式是常见的数学表达式。如果规定变量由长度不超过 8 个小写字母组成；end为保留字，表示程序段结束；用？表示输出指定变量的值，则可以设计出比较复杂的表达式（即一个可顺序执行语句序列）。例如，如果有如下语句段：

abc=10
def=8
c=abc+def
abc=abc+5-c*2
? c
? abc
end

则输出为：

c=18
abc=-21

注意：为了简化编程实现，运算符只有＋，－，＊，／，%和＾（指数运算），可以处理圆括号（），并假定输入的算术表达式正确。

要求：使用栈结构实现。

输入：表达式序列

输出：全部指定变量的值

表达式中的全部计算结果均为整数。如果在计算过程中出现除数为0的情况，则输出：Divide 0.

特殊情况说明：
在表达式中，如果操作数出现负数（例如-8），则要特别注意。例如：
10加-8表示为：10+-8。
10减-8表示为：10—8。

	测试输入	期待的输出	时间限制	内存限制
测试用例 1	以文本方式显示 abc=10↵ def=8↵ c=abc+def↵ abc=abc+5-c2↵ ? c↵ ? abc↵ end↵	以文本方式显示 c=18↵ abc=-21↵	1秒	64M
测试用例 2	以文本方式显示 a=12↵ b=5↵ c=a/b↵ d=(a+1)%(b+1)↵ e=a^2↵ f=-12+a↵ g=(a+5)d-c↵ ? c↵ ? d↵ ? e↵ ? f↵ ? g↵ a=a+10↵ ? a↵ end↵	以文本方式显示 c=2↵ d=1↵ e=144↵ f=0↵ g=15↵ a=22↵	1秒	64M
测试用例 3	以文本方式显示 abc=3↵ ab=2^(abc-1)^(5-abc)↵ ? ab↵ end↵	以文本方式显示 ab=16↵	1秒	64M
测试用例 4	以文本方式显示 a=2↵ b=a^(a+1)^(10-8)↵ ? b↵ end↵	以文本方式显示 b=512↵	1秒	64M
测试用例 5	以文本方式显示 a=10↵ ? a↵ b=-10+10↵ ? b↵ a=-10-10↵ ? a↵ c=a+-10+-10↵ ? c↵ d=-20+-8-8↵ ? d↵ e=a-12-2↵ ? e↵ f=80—10+2↵ ? f↵ g=-10—10↵ ? g↵ h=-10+-10↵ ? h↵ i=(90)↵ ? i↵ k=(-100)↵ ? k↵ end↵	以文本方式显示 a=10↵ b=0↵ a=-20↵ c=-40↵ d=-36↵ e=4↵ f=92↵ g=0↵ h=-20↵ i=90↵ k=-100↵	1秒	64M
测试用例 6	以文本方式显示 abcdefgh=4↵ ten=10↵ a=18-32↵ ? a↵ b=18/abcdefgh↵ ? b↵ c=18%(b-1)↵ ? c↵ d=ten+(ten+ten)abcdefgh↵ ? d↵ e=ten-2ten/abcdefgh↵ ? e↵ f=(18-3)3↵ ? f↵ ten=ten(ten)↵ ? ten↵ ten=ten/10↵ ten=(ten+2)/(8-ten)↵ ? ten↵ h=(23)/(52)↵ ? h↵ ten=10↵ x=ten-(80-30)/33+abcdefgh↵ y=(((2+8)2-(2+abcdefgh)/2)2-8)2↵ z=(((8+2)(abcdefgh/2)))↵ ? x↵ ? y↵ ? z↵ end↵	以文本方式显示 a=-14↵ b=4↵ c=0↵ d=90↵ e=5↵ f=45↵ ten=100↵ ten=-6↵ h=0↵ x=-34↵ y=52↵ z=20↵	1秒	64M

#include<cstdio> 
#include<string> 
#include<map> 
#include<stack> 
#include<math.h> 
#include<iostream> 
using namespace std; 
map<string, int> Varible; 
stack<char> Op; 
stack<int>  Opnum; 
string Instruction; 
string tmp; 
int GetproiIncoming(char c)    //栈外的优先级
{ 
    switch (c) 
 { 
  case('+') : return 3; 
  case('-') : return 3; 
  case('*') : return 5; 
  case('/') : return 5; 
  case('%') : return 5; 
  case('(') : return 10; 
 case('^') : return 8; 
  } 
} 
int GetproInstack(char c)   //栈内的优先级
{ 
   switch (c) 
 { 
  case('+') : return 4; 
  case('-') : return 4; 
  case('*') : return 6; 
  case('/') : return 6; 
  case('%') : return 6; 
  case('(') : return 1; 
  case('^') : return 7; 
  } 
} 
int comput(char c, int a, int b) 
{ 
    switch (c) 
 { 
  case('+') : return a+b; 
    case('-') : return a-b; 
    case('*') : return a*b; 
    case('/') : return a/b; 
    case('%') : return a%b; 
    case('^') : return (int)pow(double(a),double(b)); 
  } 
} 
int Getvar(string tmp) 
{ 
  int num = 0; 
   for (int i = 0; tmp[i]; i++) 
   { 
      if (tmp[i] >= '0'&&tmp[i] <= '9') 
        { 
          num = num * 10 + tmp[i] - '0'; 
     } 
      else if (tmp[i] >= 'a'&&tmp[i] <= 'z') 
       { 
          string var; 
            int k = i; 
         while (tmp[k] >= 'a'&&tmp[k] <= 'z') 
         { 
              k++; 
           } 
          var = tmp.substr(i, k-i); 
          Opnum.push(Varible[var]); 
          i = k - 1; 
     } 
      else if (!(tmp[i] >= '0'&&tmp[i] <= '9') && !(tmp[i] >= 'a'&&tmp[i] <= 'z')) 
       { 
          if (tmp[i] == '=') continue; 
           if ((tmp[i - 1] >= '0'&&tmp[i - 1] <= '9')) 
          { 
              Opnum.push(num); num = 0; 
          } 
          else if (!(tmp[i - 1] >= '0'&&tmp[i - 1] <= '9') && !(tmp[i - 1] >= 'a'&&tmp[i - 1] <= 'z')&&(tmp[i]=='+'||tmp[i]=='-')) 
           { 
              i++; int k = i; 
                while (tmp[k] && (tmp[k] >= '0'&&tmp[k] <= '9')) 
             { 
                  num = num * 10 + tmp[k] - '0'; k++; 
                } 
              if (tmp[i - 1] == '-') num *= -1;   i = k - 1; continue; 
           } 
          if (Op.empty()||tmp[i]=='(') 
           { 
              Op.push(tmp[i]); continue; 
         } 
          else if (tmp[i] == ')') 
            { 
              char op; 
               while (!Op.empty() && (op = Op.top()) != '(') 
              { 
                  int b = Opnum.top(); Opnum.pop(); 
                  int a = Opnum.top(); Opnum.pop(); 
                  if (b == 0 && op == '/') 
                       continue; 
                  else { Opnum.push(comput(op,a,b)); } 
                   Op.pop(); 
              } 
              Op.pop(); 
            } 
            else 
           { 
              int Incoming = GetproiIncoming(tmp[i]); 
                int Instack; 
               char op; 
               while (!Op.empty()&&(Instack = GetproInstack(Op.top())) > Incoming) 
             { 
                  op = Op.top(); 
                 int b = Opnum.top(); Opnum.pop(); 
                  int a = Opnum.top(); Opnum.pop(); 
                  if (b == 0 && op == '/') 
                       continue; 
                  else { Opnum.push(comput(op, a, b)); } 
                 Op.pop(); 
              } 
              Op.push(tmp[i]); 
           } 
      } 
  } 
  if (tmp[tmp.length()-1] >= '0'&&tmp[tmp.length()-1] <= '9') 
      Opnum.push(num); 
   if (!Op.empty()||!Opnum.empty()) 
   { 
     while (!Op.empty()) 
        { 
          char op = Op.top(); 
            int b = Opnum.top(); Opnum.pop(); 
          int a = Opnum.top(); Opnum.pop(); 
          if (b == 0 && op == '/') 
               continue; 
          else { Opnum.push(comput(op, a, b)); } 
         Op.pop(); 
      } 
      return Opnum.top(); 
    } 
  else return num; 
} 
int main() 
{ 
    //freopen("1.txt", "r", stdin); 
    while (getline(cin,Instruction)) 
   { 
      if (Instruction == "end") 
          break; 
     while (!Op.empty()) 
            Op.pop(); 
      while (!Opnum.empty()) 
         Opnum.pop(); 
       if (Instruction[0] == '?') 
     { 
          tmp = Instruction.substr(2); 
           int num = Varible.find(tmp)->second; 
            cout << tmp<< '='<<num<< endl; 
     } 
      else if (Instruction[0] >= 'a'&&Instruction[0] <= 'z') 
       { 
          int i = 0; 
         string varble; 
         while (Instruction[i] != '=') 
          { 
              i++; 
           } 
          varble = Instruction.substr(0, i); 
         if (Varible.count(varble) == 0) 
            { 
              Varible[varble] = 0; 
           } 
          string tmp = Instruction.substr(i); 
            Varible[varble] = Getvar(tmp); 
     } 
  } 
  return 0; 
}