Complicated Expressions(表达式转换)

题意：给出一个表达式可能含有多余的括号，去掉多余的括号，输出它的最简形式。
思路：先将表达式转化成后缀式，因为后缀式不含括号，然后再转化成中缀式，并根据运算符的优先级添加括号。
  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <string>
  4 #include <stack>
  5 #include <iostream>
  6 using namespace std;
  7 char ss[1010];
  8 int f(char ch)
  9 {
 10     if(ch=='(')
 11         return 0;
 12     else if(ch=='+'||ch=='-')
 13         return 1;
 14     else if (ch=='*'||ch=='/')
 15         return 2;
 16 }
 17 void change1(string s)
 18 {
 19     int l = 0;
 20     stack<char>p;
 21     while(!p.empty()) p.pop();
 22     for (int i = 0; i < s.size(); i++)
 23     {
 24         if(s[i]>='a'&&s[i]<='z')
 25             ss[l++]=s[i];
 26         else
 27         {
 28             if (s[i]=='(')
 29                 p.push(s[i]);
 30             else if (s[i]==')')
 31             {
 32                 while(!p.empty())
 33                 {
 34                     char ch = p.top();
 35                     p.pop();
 36                     if(ch=='(')
 37                         break;
 38                     ss[l++] = ch;
 39                 }
 40             }
 41             else
 42             {
 43                 while(!p.empty()&&f(p.top())>=f(s[i]))
 44                 {
 45                     char ch = p.top();
 46                     p.pop();
 47                     ss[l++] = ch;
 48                 }
 49                 p.push(s[i]);
 50             }
 51 
 52         }
 53     }
 54 }
 55 while(!p.empty())
 56 {
 57     ss[l++] = p.top();
 58     p.pop();
 59 }
 60 ss[l++]='';
 61 }
 62 void change2(char a[])
 63 {
 64     string s1, s2, s3, fl, fs;
 65     string s[300];
 66     char f[300];
 67     int top = 0;
 68     s1 = a;
 69     for(int i = 0; i < (int)s1.length(); i++)
 70     {
 71         if(s1[i]>='a' && s1[i]<='z')
 72         {
 73             fl = s1[i];
 74             top++;
 75             s[top] = s1[i];
 76         }
 77         else if(s1[i]=='+')
 78         {
 79             s2 = s[top];
 80             top--;
 81             s3 = s[top];
 82             top--;
 83             top++;
 84             s[top] = s3+'+'+s2;
 85             f[top] = '+';
 86         }
 87         else if(s1[i]=='-')
 88         {
 89             s2 = s[top];
 90             top--;
 91             s3 = s[top];
 92             top--;
 93             if(f[top+2]=='+' || f[top+2]=='-')
 94             {
 95                 if(s2.length()>1) s2 = '('+s2+')';
 96             }
 97             top++;
 98             s[top] = s3+'-'+s2;
 99             f[top] = '-';
100         }
101         else if(s1[i]=='*')
102         {
103             s2 = s[top];
104             top--;
105             s3 = s[top];
106             top--;
107             if(f[top+1]=='+' || f[top+1]=='-')
108             {
109                 if(s3.length()>1) s3 = '('+s3+')';
110             }
111             if(f[top+2]=='+' || f[top+2]=='-')
112             {
113                 if(s2.length()>1) s2 = '('+s2+')';
114             }
115             top++;
116             s[top] = s3+'*'+s2;
117             f[top] = '*';
118         }
119         else if(s1[i]=='/')
120         {
121             s2 = s[top];
122             top--;
123             s3 = s[top];
124             top--;
125             if(f[top+1]=='+' || f[top+1]=='-')
126             {
127                 if(s3.length()>1) s3 = '('+s3+')';
128             }
129             if(f[top+2]=='+' || f[top+2]=='-' || f[top+2]=='*' || f[top+2]=='/')
130             {
131                 if(s2.length()>1) s2='('+s2+')';
132             }
133             top++;
134             s[top] = s3+'/'+s2;
135             f[top] = '/';
136         }
137     }
138     cout<<s[1]<<endl;
139 }
140 int main()
141 {
142 
143     //freopen("expr.in", "r", stdin);
144     //freopen("ss.out", "w", stdout);
145     int t;
146     string s;
147     cin>>t;
148     while(t--)
149     {
150         cin>>s;
151         change1(s);
152         change2(ss);
153     }
154     return 0;
155 }
View Code