今天做了個題，主要就是判斷兩個算術表達式是否相等，當然是用棧了，先將表達式轉化為后綴表達式，然后棧求值
1
/**//*Source Code
2
3Problem: 1686 User: Torres
4Memory: 224K Time: 0MS
5Language: C++ Result: Accepted
6
7
Source Code */
8
#include<iostream>
9#include<string>
10#include<stack>
11#include<map>
12using namespace std;
13
14map<char,int>mp;
15
16bool isletter(char &c)
17
{
18 if(c>='a'&&c<='z'||c>='A'&&c<='Z'||c>='1'&&c<='9')
19 return true;
20 else return false;
21}
22
23string change(char str[])
24{
25 int i,j;
26 int len=strlen(str);
27 string temp;
28 char ch[200];
29 stack<char> cs;
30 for(i=0,j=0;i<len;i++)
31 if(isletter(str[i]))ch[j++]=str[i];
32
else{
33 switch(str[i]){
34 case '(':cs.push(str[i]);break;
35 case ')':
36 while(cs.top()!='('){
37 ch[j++]=cs.top();
38 cs.pop();
39
}
40 cs.pop();
41 break;
42 case '+':
43 case '-':
44 case '*':
45 while(!cs.empty()&&mp[str[i]]<=mp[cs.top()]){
46 ch[j++]=cs.top();
47 cs.pop();
48 }
49 cs.push(str[i]);
50 break;
51 }
52 }
53 while(!cs.empty())ch[j++]=cs.top(),cs.pop();
54 ch[j]='\0';
55 temp=ch;
56 return temp;
57}
58
59int result(string &str)
60{
61 int i;
62 int len=str.size();
63 stack<int> re;
64 for(i=0;i<len;i++)
65 if(isletter(str[i]))
66 {
67 if(str[i]>='1'&&str[i]<='9')
68 re.push(str[i]-'0');
69 else
70 re.push((int)str[i]);
71 }
72 else{
73 int a,anext,b;
74 a=re.top();
75 re.pop();
76 anext=re.top();
77 re.pop();
78 switch(str[i]){
79 case'+':b=a+anext;re.push(b);break;
80 case'-':b=anext-a;re.push(b);break;
81 case'*':b=a*anext;re.push(b);break;
82 }
83 }
84 return re.top();
85}
86
87int main()
88{
89 int N,ca;
90 char str1[100],str2[100];
91 mp['+']=1;
92 mp['-']=1;
93 mp['*']=2;
94 mp['(']=0;
95 scanf("%d",&N);
96 getchar();
97 for(ca=1;ca<=N;ca++){
98 gets(str1);
99 gets(str2);
100 string temp1,temp2;
101 temp1=change(str1);
102 temp2=change(str2);
103 int re1=result(temp1);
104 int re2=result(temp2);
105 if(re1==re2)printf("YES\n");
106 else printf("NO\n");
107 }
108 return 0;
109}
110
111