lazy instructor，lazyinstructor

lazy instructor，lazyinstructor

Description

A math instructor is too lazy to grade a question in the exam papers in which students are supposed to produce a complicated formula for the question asked. Students may write correct answers in different forms which makes grading very hard. So, the instructor needs help from computer programmers and you can help. 

You are to write a program to read different formulas and determine whether or not they are arithmetically equivalent. 

Input

The first line of the input contains an integer N (1 <= N <= 20) that is the number of test cases. Following the first line, there are two lines for each test case. A test case consists of two arithmetic expressions, each on a separate line with at most 80 characters. There is no blank line in the input. An expression contains one or more of the following: 

• Single letter variables (case insensitive). 
• Single digit numbers. 
• Matched left and right parentheses. 
• Binary operators +, - and * which are used for addition, subtraction and multiplication respectively. 
• Arbitrary number of blank or tab characters between above tokens.

Note: Expressions are syntactically correct and evaluated from left to right with equal precedence (priority) for all operators. The coefficients and exponents of the variables are guaranteed to fit in 16-bit integers. 

Output

Your program must produce one line for each test case. If input expressions for each test data are arithmetically equivalent, "YES", otherwise "NO" must be printed as the output of the program. Output should be all in upper-case characters.

Sample Input

3
(a+b-c)*2
(a+a)+(b*2)-(3*c)+c
a*2-(a+c)+((a+c+e)*2)
3*a+c+(2*e)
(a-b)*(a-b)
(a*a)-(2*a*b)-(b*b)

Sample Output

YES
YES
NO



題目意思：輸入兩行公式，判斷這兩行公式相不相等，如果相等，輸出YES，否則輸出NO

解題思路：先將方式變成後綴式，後綴式通過棧實現。（不曉得後綴式是什麼，就百度後綴式吧，我也是百度的(⊙﹏⊙)b）  
變成後綴式之後，再通過棧計算他們的值，這裡需要將字母轉為ASCII碼的值計算。最後判斷.......

  1 #include <map>
  2 #include <stack>
  3 #include <cctype>
  4 #include <iostream>
  5 using namespace std;
  6 map<char,int> m;
  7 string a1,a2,v1,v2;
  8 string bianhouzui(string a)   //這裡是將公式變成後綴式
  9 {
 10     int i,j=0,len;
 11     char c[81];
 12     stack<char> z1;
 13     len=a.size();
 14     for(i=0; i<len; i++)
 15     {
 16         if(isalnum(a[i]))   //isalnum是判斷是不是數字或者字母，如果是返回真
 17             c[j++]=a[i];
 18         else
 19         {
 20             switch (a[i])
 21             {
 22             case '(':
 23                 z1.push(a[i]);
 24                 break;
 25             case ')':
 26                 while(z1.top()!='(')
 27                 {
 28                     c[j++]=z1.top();
 29                     z1.pop();
 30                 }
 31                 z1.pop();
 32                 break;
 33             case '+':
 34             case '-':
 35             case '*':
 36                 while(!z1.empty()&&m[a[i]]<=m[z1.top()])
 37                 {
 38                     c[j++]=z1.top();
 39                     z1.pop();
 40                 }
 41                 z1.push(a[i]);
 42             }
 43         }
 44     }
 45     while(!z1.empty())
 46     {
 47         c[j++]=z1.top();
 48         z1.pop();
 49     }
 50     c[j]='\0';
 51     string x=c;
 52     return x;
 53 }
 54 
 55 
 56 int jisuan(string v)   //這裡是計算
 57 {
 58     int a,b,i,len;
 59     len=v.size();
 60     stack<int> z2;
 61     for(i=0; i<len; i++)
 62     {
 63         if(isalnum(v[i]))
 64         {
 65             if(isdigit(v[i]))  //  判斷是不是數字
 66                 z2.push(v[i]-'0');   //轉成ASCII碼
 67             else
 68                 z2.push(v[i]);
 69         }
 70         else
 71         {
 72             a=z2.top();
 73             z2.pop();
 74             b=z2.top();
 75             z2.pop();
 76             switch (v[i])
 77             {
 78             case '+':
 79                 z2.push(b+a);
 80                 break;
 81             case '-':
 82                 z2.push(b-a);
 83                 break;
 84             case '*':
 85                 z2.push(b*a);
 86             }
 87         }
 88     }
 89     return z2.top();
 90 }
 91 
 92 
 93 int main()
 94 {
 95     int T;
 96     m['(']=0;
 97     m['+']=m['-']=1;
 98     m['*']=2;
 99     cin>>T;
100     cin.get();     //沒有這個就不行，我也不知道為什麼，貌似好像是什麼回車問題.....
101     while(T--)
102     {
103         getline(cin,a1);
104         getline(cin,a2);
105         v1= bianhouzui(a1);
106         v2=  bianhouzui(a2);
107         if(jisuan(v1)==jisuan(v2))
108             cout<<"YES"<<endl;
109         else
110             cout<<"NO"<<endl;
111     }
112     return 0;
113 }