首页 > 代码库 > 中缀表达式求值总结
中缀表达式求值总结
中缀表达式的题目困扰了我两三年，都没去写过。。这两天看到2005年提高组的T3要用到所以心血来潮写了一下。
表达式求值借助基本结构应该不用说了是栈，不管手写还是STL都没有太大关系。而中缀表达式最难控制的地方是优先级，算上+-*/^（）一共有四个优先级【+-，*/，， ^（）】（后面会提到一个三级的字符“负号”，这是预留空位）。
下面对一个例子进行分析：2*3+4*6/3+17-4^2
那么处理的时候怎么控制优先级呢？
搜到‘+’之前，栈的情况是这样的：
操作数栈：2 3
操作符栈：*
然后搜到+的时候因为*的优先级大，所以计算 2*3 ，并把结果6入栈，+入栈。
然后搜到‘/’之前，栈的情况是这样的：
操作数栈：6 4 6
操作符栈：+ *
因为*的优先级和/是一样的，所以先计算4*6，把结果24入栈，/入栈。
以此类推，可以计算出整个式子的值
然后来讨论负号问题。
‘-’可以当做减号，也可以当做负号。根据经验可知，如果‘-’前面是‘)‘或者数字的时候用作减号，否则为负号。这里我要引用一位神犇的方法，把‘-’改为另一个负号比如说‘#’，优先级为3级（就是前面说的）。
这样的话比如表达式-1+5就可以改为#1+5，计算的时候是先计算栈底的‘#’，因此答案为4。
接下来要加入括号。我的解决方法是把括号看做一个独立的表达式，进行递归处理，每次完整计算一个括号内的表达式的值（毕竟这才符合计算规律）。
于是就有了这样的代码（用了一下quicksum）（我删了几个函数）
1 #include <iostream> 2 #include <string> 3 #include <stack> 4 #include <map> 5 using namespace std; 6 7 string s; 8 stack<int> a; 9 stack<char> b; 10 map<char,int> mp; 11 int len; 12 int it; 13 14 int qsum(int a,int b) 15 { 16 int r=1; 17 while (b) 18 { 19 if (b&1) r*=a; 20 a*=a; 21 b>>=1; 22 } 23 return r; 24 } 25 26 void ct() 27 { 28 int tmp=a.top();a.pop(); 29 char cc=b.top();b.pop(); 30 if (cc==‘#‘) 31 { 32 a.push(0-tmp); 33 return; 34 } 35 int tp=a.top();a.pop(); 36 switch (cc) 37 { 38 case ‘+‘:a.push(tmp+tp);break; 39 case ‘-‘:a.push(tp-tmp);break; 40 case ‘*‘:a.push(tmp*tp);break; 41 case ‘/‘:a.push(tp/tmp);break; 42 case ‘^‘:a.push(qsum(tp,tmp));break; 43 } 44 } 45 46 void calc() 47 { 48 int xx=0; 49 b.push(s[it]); 50 it++; 51 if (s[it]==‘)‘) 52 { 53 b.pop();return; 54 } 55 while (s[it]!=‘)‘) 56 { 57 if (isdigit(s[it])) 58 { 59 xx=xx*10+s[it]-‘0‘; 60 } 61 else 62 { 63 if (isdigit(s[it-1])) 64 { 65 a.push(xx); 66 xx=0; 67 } 68 switch (s[it]) 69 { 70 case ‘(‘:calc();break; 71 case ‘+‘: 72 if (mp[b.top()]>=1&&b.top()!=‘(‘&&b.top()!=‘)‘) 73 ct(); 74 b.push(s[it]); 75 break; 76 case ‘-‘: 77 if (mp[b.top()]>=1&&b.top()!=‘(‘&&b.top()!=‘)‘) 78 ct(); 79 b.push(s[it]); 80 break; 81 case ‘*‘: 82 if (mp[b.top()]>=2&&b.top()!=‘(‘&&b.top()!=‘)‘) 83 ct(); 84 b.push(s[it]); 85 break; 86 case ‘/‘: 87 if (mp[b.top()]>=2&&b.top()!=‘(‘&&b.top()!=‘)‘) 88 ct(); 89 b.push(‘/‘); 90 break; 91 case ‘^‘: 92 if (mp[b.top()]>=4&&b.top()!=‘(‘&&b.top()!=‘)‘) 93 ct(); 94 b.push(s[it]); 95 break; 96 case ‘#‘: 97 b.push(s[it]); 98 } 99 }100 it++;101 }102 if (s[it-1]!=‘)‘)103 a.push(xx);104 while (b.top()!=‘(‘)105 ct();106 b.pop();107 }108 109 int main()110 {111 cin >> s;112 mp[‘+‘]=1;mp[‘-‘]=1;mp[‘#‘]=3;mp[‘*‘]=2;113 mp[‘^‘]=4;mp[‘(‘]=4;mp[‘)‘]=4;mp[‘/‘]=2;114 pipei();115 len=s.size();116 for (int i=0;i<len;i++)117 {118 if (i==0 && s[i]==‘-‘)119 s[i]=‘#‘;120 else121 {122 if (s[i]==‘-‘ && !isdigit(s[i-1]) && s[i-1]!=‘)‘)123 s[i]=‘#‘;124 }125 }126 int tmp=0,x=0;127 for (it=0;it<len;it++)128 {129 if (isdigit(s[it]))130 {131 x=x*10+s[it]-‘0‘;132 }133 else134 {135 if (isdigit(s[it-1]))136 {137 a.push(x);138 x=0;139 }140 if (s[it]==‘(‘)141 {142 calc();143 continue;144 }145 if (!b.empty())146 {147 switch (s[it])148 {149 case ‘+‘:150 if (mp[b.top()]>=1)151 ct();152 b.push(s[it]);153 break;154 case ‘-‘:155 if (mp[b.top()]>=1)156 ct();157 b.push(s[it]);158 break;159 case ‘*‘:160 if (mp[b.top()]>=2)161 ct();162 b.push(s[it]);163 break;164 case ‘/‘:165 if (mp[b.top()]>=2)166 ct();167 b.push(‘/‘);168 break;169 case ‘^‘:170 if (mp[b.top()]>=4)171 ct();172 b.push(s[it]);173 break;174 case ‘#‘:175 b.push(s[it]);176 }177 }178 else179 b.push(s[it]);180 }181 }182 if (s[it-1]!=‘)‘)183 a.push(x);184 while (!b.empty())185 ct();186 cout << a.top() << "\n";187 }
然后codevs上有一题有多余括号问题。既然出了这样的题目就表示多余的括号可以随便匹配咯所以我弄了很无聊的匹配（我居然往里面加括号woc）于是这是我单独处理括号的代码（只是多加了[]和{}）。
1 #include <iostream> 2 #include <cstdio> 3 #include <string> 4 #include <stack> 5 using namespace std; 6 7 string s; 8 stack<pair<char,int> > c; 9 bool v[100001];10 11 void ist(int pos)12 {13 switch (s[pos])14 {15 case‘)‘:s.insert(pos,"(");break;16 case‘]‘:s.insert(pos,"[");break;17 case‘}‘:s.insert(pos,"{");18 }19 }20 21 int main()22 {23 cin >> s;24 for (int i=0;i<s.size();i++)25 {26 pair<char,int> ss;27 ss.first=s[i];ss.second=i;28 switch (s[i])29 {30 case ‘(‘:c.push(ss);v[i]=1;break;31 case ‘[‘:c.push(ss);v[i]=1;break;32 case ‘{‘:c.push(ss);v[i]=1;break;33 case ‘)‘:if (i==0) ist(i);34 if (!c.empty() && c.top().first==‘(‘)35 {36 v[c.top().second]=0;37 c.pop();38 }39 else40 {41 ist(i);42 i++;43 }44 break;45 case ‘]‘:if (i==0) ist(i);46 if (!c.empty() && c.top().first==‘[‘)47 {48 v[c.top().second]=0;49 c.pop();50 }51 else52 {53 ist(i);54 i++;55 }56 break;57 case ‘}‘:if (i==0) ist(i);58 if (!c.empty() && c.top().first==‘{‘)59 {60 v[c.top().second]=0;61 c.pop(); 62 }63 else64 {65 ist(i);66 i++;67 }68 }69 }70 for(int i=s.size();i>=0;i--)71 if (v[i])72 {73 switch(s[i])74 {75 case ‘(‘:s.insert(i+1,")");break;76 case ‘[‘:s.insert(i+1,"]");break;77 case ‘{‘:s.insert(i+1,"}");78 }79 }80 cout << s;81 }
结合了一下变成超长的代码了。。。可以AC掉codevs上的2178哦
1 #include <iostream> 2 #include <string> 3 #include <stack> 4 #include <map> 5 using namespace std; 6 7 string s; 8 stack<int> a; 9 stack<char> b; 10 map<char,int> mp; 11 int len; 12 int it; 13 stack<pair<char,int> > c; 14 bool v[100001]; 15 16 int qsum(int a,int b) 17 { 18 int r=1; 19 while (b) 20 { 21 if (b&1) r*=a; 22 a*=a; 23 b>>=1; 24 } 25 return r; 26 } 27 28 void ct() 29 { 30 int tmp=a.top();a.pop(); 31 char cc=b.top();b.pop(); 32 if (cc==‘#‘) 33 { 34 a.push(0-tmp); 35 return; 36 } 37 int tp=a.top();a.pop(); 38 switch (cc) 39 { 40 case ‘+‘:a.push(tmp+tp);break; 41 case ‘-‘:a.push(tp-tmp);break; 42 case ‘*‘:a.push(tmp*tp);break; 43 case ‘/‘:a.push(tp/tmp);break; 44 case ‘^‘:a.push(qsum(tp,tmp));break; 45 } 46 } 47 48 void calc() 49 { 50 int xx=0; 51 b.push(s[it]); 52 it++; 53 if (s[it]==‘)‘) 54 { 55 b.pop();return; 56 } 57 while (s[it]!=‘)‘) 58 { 59 if (isdigit(s[it])) 60 { 61 xx=xx*10+s[it]-‘0‘; 62 } 63 else 64 { 65 if (isdigit(s[it-1])) 66 { 67 a.push(xx); 68 xx=0; 69 } 70 switch (s[it]) 71 { 72 case ‘(‘:calc();break; 73 case ‘+‘: 74 if (mp[b.top()]>=1&&b.top()!=‘(‘&&b.top()!=‘)‘) 75 ct(); 76 b.push(s[it]); 77 break; 78 case ‘-‘: 79 if (mp[b.top()]>=1&&b.top()!=‘(‘&&b.top()!=‘)‘) 80 ct(); 81 b.push(s[it]); 82 break; 83 case ‘*‘: 84 if (mp[b.top()]>=2&&b.top()!=‘(‘&&b.top()!=‘)‘) 85 ct(); 86 b.push(s[it]); 87 break; 88 case ‘/‘: 89 if (mp[b.top()]>=2&&b.top()!=‘(‘&&b.top()!=‘)‘) 90 ct(); 91 b.push(‘/‘); 92 break; 93 case ‘^‘: 94 if (mp[b.top()]>=4&&b.top()!=‘(‘&&b.top()!=‘)‘) 95 ct(); 96 b.push(s[it]); 97 break; 98 case ‘#‘: 99 b.push(s[it]);100 }101 }102 it++;103 }104 if (s[it-1]!=‘)‘)105 a.push(xx);106 while (b.top()!=‘(‘)107 ct();108 b.pop();109 }110 111 void ist(int pos)112 {113 switch (s[pos])114 {115 case‘)‘:s.insert(pos,"(");break;116 case‘]‘:s.insert(pos,"[");break;117 case‘}‘:s.insert(pos,"{");118 }119 }120 121 void pipei()122 {123 for (int i=0;i<s.size();i++)124 {125 pair<char,int> ss;126 ss.first=s[i];ss.second=i;127 switch (s[i])128 {129 case ‘(‘:c.push(ss);v[i]=1;break;130 case ‘[‘:c.push(ss);v[i]=1;break;131 case ‘{‘:c.push(ss);v[i]=1;break;132 case ‘)‘:if (i==0) ist(i);133 if (!c.empty() && c.top().first==‘(‘)134 {135 v[c.top().second]=0;136 c.pop();137 }138 else139 {140 ist(i);141 i++;142 }143 break;144 case ‘]‘:if (i==0) ist(i);145 if (!c.empty() && c.top().first==‘[‘)146 {147 v[c.top().second]=0;148 c.pop();149 }150 else151 {152 ist(i);153 i++;154 }155 break;156 case ‘}‘:if (i==0) ist(i);157 if (!c.empty() && c.top().first==‘{‘)158 {159 v[c.top().second]=0;160 c.pop(); 161 }162 else163 {164 ist(i);165 i++;166 }167 }168 }169 for(int i=s.size();i>=0;i--)170 if (v[i])171 {172 switch(s[i])173 {174 case ‘(‘:s.insert(i+1,")");break;175 case ‘[‘:s.insert(i+1,"]");break;176 case ‘{‘:s.insert(i+1,"}");177 }178 }179 }180 181 int main()182 {183 cin >> s;184 mp[‘+‘]=1;mp[‘-‘]=1;mp[‘#‘]=3;mp[‘*‘]=2;185 mp[‘^‘]=4;mp[‘(‘]=4;mp[‘)‘]=4;mp[‘/‘]=2;186 pipei();187 len=s.size();188 for (int i=0;i<len;i++)189 {190 if (i==0 && s[i]==‘-‘)191 s[i]=‘#‘;192 else193 {194 if (s[i]==‘-‘ && !isdigit(s[i-1]) && s[i-1]!=‘)‘)195 s[i]=‘#‘;196 }197 }198 int tmp=0,x=0;199 for (it=0;it<len;it++)200 {201 if (isdigit(s[it]))202 {203 x=x*10+s[it]-‘0‘;204 }205 else206 {207 if (isdigit(s[it-1]))208 {209 a.push(x);210 x=0;211 }212 if (s[it]==‘(‘)213 {214 calc();215 continue;216 }217 if (!b.empty())218 {219 switch (s[it])220 {221 case ‘+‘:222 if (mp[b.top()]>=1)223 ct();224 b.push(s[it]);225 break;226 case ‘-‘:227 if (mp[b.top()]>=1)228 ct();229 b.push(s[it]);230 break;231 case ‘*‘:232 if (mp[b.top()]>=2)233 ct();234 b.push(s[it]);235 break;236 case ‘/‘:237 if (mp[b.top()]>=2)238 ct();239 b.push(‘/‘);240 break;241 case ‘^‘:242 if (mp[b.top()]>=4)243 ct();244 b.push(s[it]);245 break;246 case ‘#‘:247 b.push(s[it]);248 }249 }250 else251 b.push(s[it]);252 }253 }254 if (s[it-1]!=‘)‘)255 a.push(x);256 while (!b.empty())257 ct();258 cout << a.top() << "\n";259 }
好啦就这样吧。
中缀表达式求值总结
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。