今天做了个题,主要就是判断两个算术表达式是否相等,当然是用栈了,先将表达式转化为后缀表达式,然后栈求值
1
/**//*Source Code
2
3
Problem: 1686 User: Torres
4
Memory: 224K Time: 0MS
5
Language: C++ Result: Accepted
6
7
Source Code */
8
#include<iostream>
9
#include<string>
10
#include<stack>
11
#include<map>
12
using namespace std;
13
14
map<char,int>mp;
15
16
bool 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
23
string 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
59
int 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
87
int 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