栈

Time Limit:1000MS Memory Limit:10000KB 64bit IO Format:%I64d & %I64u

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


这道题需要先对原始数据进行转换，让它变成容易处理的公式。
例如

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

转换之后：

ab+c-2*
aa+b2*+3c*-c+

一般步骤为：
准备两个栈，一个为元素栈简称栈A，一个运算符栈，简称栈B

遍历整个字符串1~n

if ai为元素，入栈A

else

if ai为（直接入栈B

if ai为）将栈B全部出栈，加入栈A

if ai为+-*/ 比较其与栈B栈顶元素的运算优先级，如果栈顶元素优先级大于等于它，那么把这些元素都加入A，直到栈顶元素优先级小于它，把它加入B

#include <iostream>
#include <cstdio>
#include <ctype.h>
#include <map>
#include <cstring>
#include <stack>
typedef struct
{
    char a[100];
    int length;
}sqlist;
using namespace std;map<char, int> mat;
string a,b;

int caculate(string s)
{
    sqlist Q;
    Q.length=0;
    stack<char> sh;
    for(int i=0;i<s.size();i++)
    {

      if(isalnum(s[i]))  Q.a[++Q.length]=s[i];
      else
      switch(s[i])
      {
      case '(': sh.push('(');break;
      case ')':
        while(sh.top()!='(')
        {
            Q.a[++Q.length]=sh.top();
            sh.pop();
        }
        sh.pop();break;
      case '+':case '-':case '*':case '/':
        while(!sh.empty()&&mat[sh.top()]>=mat[s[i]])
        {
            Q.a[++Q.length]=sh.top();
            sh.pop();
        }
        sh.push(s[i]);
      }
      /*printf("%d
",i);
      for(int j=1;j<=Q.length;j++) printf("%c ",Q.a[j]);
        puts("");*/
    }
    while(!sh.empty())
    {
        Q.a[++Q.length]=sh.top();
        sh.pop();
    }
    stack<int>st;
    for(int i=1;i<=Q.length;i++)
    {
        if(isalnum(Q.a[i])) st.push(Q.a[i]-'0');
        else
        {
            int a=st.top();
            st.pop();
            int b=st.top();
            st.pop();
            switch(Q.a[i])
            {
                case '+':st.push(b+a);break;
                case '-':st.push(b-a);break;
                case '*':st.push(b*a);break;
                case '/':st.push(b/a);break;
            }
        }
    }
    return st.top();
}
int main()
{
    int T;
    scanf("%d",&T);getchar();
    mat['(']=0;
    mat['+']=mat['-']=1;
    mat['*']=mat['/']=2;
    while(T--)
    {
        getline(cin,a);
        getline(cin,b);
        if(caculate(a)==caculate(b))
            printf("YES
");
        else
            printf("NO
");
    }
    return 0;
}

View Code