题解:
考察点: 栈,模拟
易错点:
由于习惯,日常生活中接触的一般为中缀表达式,导致很多同学不太明白什么是后缀表达式。后缀表达式被称为逆波兰式,是将运算符写在操作数之后的一种形式。简单来说就是如果存在E1 op E2形式的表达式,op是任意二元操作符,则E的后缀式为E1'E2' op,E1'和E2'分别为E1和E2的后缀式。有关后缀表达式的介绍可以参看百度百科
解法:栈
根据易错点中介绍的后缀表达式的知识,则有了如下思路。用一个栈来维护中缀表达式中的操作符,首先,遍历中缀表达式中的每个字符,如果是字母就直接输出,作为后缀表达式的一部分;如果是操作符,则比较其和栈顶元素的优先级,如果优先级低于栈顶元素,则将栈中元素依次出栈,直到栈为空,或者栈中元素的优先级低于当前元素,然后把该元素压栈。最后遍历完字符串之后把栈中元素全部出栈即可
#include "bits/stdc++.h" using namespace std; string s; stack<char>p; int main() { cin>>s; unordered_map<char,int>mp; mp['+']=1,mp['-']=1,mp['*']=2,mp['/']=2; int len=s.length(); for(int i=0;i<len;i++){ if(s[i]>='a'&&s[i]<='z') cout<<s[i]; else{ while(!p.empty()&&[s[i]]<=mp[p.top()]){ cout<<p.top(); p.pop(); } p.push(s[i]); } } while(!p.empty()){ cout<<p.top(); p.pop(); } cout<<endl; }