poj1686

http://poj.org/problem?id=1686
2つの式が正しいかどうかを判断するのは、2つの式が同じかどうかを判断するのではなく、判断結果である.

           ，    ，       
  ：
//         
//    ：
//1.        ，      ，        .(            ）
//2.                      ，            ，   。  ，  。
//3.  （，  ，    ）  。
#include<iostream>
#include<cstdio>
#include<string.h>
#include<map>
#include<stack>
#define max 101
using namespace std;
map<char,int> ma;
char root[max];
int Judge(char a)
{
    if(a>='a'&&a<='z'||a>='A'&&a<='Z'||a>='1'&&a<='9')
     return 1;
     return 0;
}
void Convert(char ch[])
{
    /* for(int i=0;i<strlen(ch);i++)
         printf("%c",ch[i]);
         printf("
");
         */
    stack<char> start;
    int len=strlen(ch);
   // printf("%d
",len);
    int i;
    int Top=0;
    for(i=0;i<len;i++)
    {
        if(Judge(ch[i]))
        {
            root[Top++]=ch[i];
        }
        else
        {
          switch( ch[i] )
          {
         //     printf("fdsdfsd
");
              case '(':
                  start.push( ch[i] );
                  break;
              case ')':
                  while(start.top()!='(')
                  {
                      root[Top++]=start.top();// （）          。
                      start.pop();
                  }
                  start.pop();//pop() ')';
                  break;
             case '+':
             case '-':
             case '*':
             while((!start.empty())&&ma[start.top()]>=ma[ch[i]])
             {
                 root[Top++]=start.top();
                 start.pop();
             }
              start.push(ch[i]);
              break;
          }

        }
    }
    while(!start.empty())
    {
        root[Top++]=start.top();
        start.pop();
    }
    root[Top]=0;
}
int sum()
{
    stack<int> end;
    int len=strlen(root);
    int i;
    for( i=0;i<len;i++)
    {
        if(Judge(root[i]))
        {
            if(root[i]>='1'&&root[i]<='9')
              end.push(root[i]-'0');
            else
             end.push((int)root[i]);
        }
        else
        {
            int num1,num2;
            num1=end.top();
            end.pop();

            num2=end.top();
            end.pop();

            switch(root[i])
            {
                case '*':
                 end.push(num1*num2);
                 break;
                case '-':
                end.push(num2-num1);
                break;
                case '+':
                end.push(num1+num2);
                break;
            }
        }
    }
    return end.top();
}
int main()
{
    char cha1[max],cha2[max];
    int N;

     ma['+']=2;
     ma['-']=2;
     ma['*']=3;
     ma['(']=1;
     cin>>N;
    getchar();
    int a,b;
    while(N--)
    {
        cin.getline(cha1,100,'
');
        cin.getline(cha2,100,'
');
        Convert(cha1);
        a=sum();
        Convert(cha2);
        b=sum();
        if(a==b)
          cout<<"YES"<<endl;
        else
          cout<<"NO"<<endl;
    }
    return 0;
}