对于考研而言,这种东西一般应该只会设计到+-*/()和正整数。 那么写起来就很好办了。
抄一下课本上的两个结论:
1.在扫描exp遇到一个运算符op时,如果栈为空,直接将其进栈, 如果栈不为空,只有当op的优先级高于栈顶运算符的优先级的时候才把op进栈, 否则依次出栈运算符并存入postexp,直到栈顶的运算符的优先级小于op的优先级为止, 然后再将op进栈。
2.在扫描exp时遇到(,那么直接入栈,如果遇到),那么不断出栈直至把一个(出栈。
代码:
#include<bits/stdc++.h> using namespace std; stack<char> sta; bool isDigital(char c) { if(c>='0'&&c<='9')return 1; return 0; } int main() { freopen("in.txt","r",stdin); while(cin.peek()!='\n'&&cin.peek()!=EOF) { char c=cin.peek(); //处理数字 if(isDigital(c)) { string str=""; while(isDigital(c)||c=='.') { str+=c; cin.get(); c=cin.peek(); } cout<<str; } else { //处理+-*/() if(c=='(') cin.get(),sta.push(c); if(c==')') { cin.get(); while(sta.top()!='(') { cout<<sta.top(); sta.pop(); } sta.pop(); } if(c=='+'||c=='-') { cin.get(); while(sta.size()!=0&&sta.top()!='(') { cout<<sta.top(); sta.pop(); } sta.push(c); } if(c=='*'||c=='/') { cin.get(); while(sta.top()=='*'||sta.top()=='/') { cout<<sta.top(); sta.pop(); } sta.push(c); } } } while(sta.size()) { cout<<sta.top(); sta.pop(); } return 0; }
但是在acm里,就又多了正负数,小数。
#include<iostream> #include<stack> #include<cstring> #include<iomanip> using namespace std; stack<char> sta; string str; char c; char last='1'; void solve() { while(cin.peek()!='\n') { c=cin.get(); //cout<<"what"<<endl; //cout<<c<<endl; if(c>='0'&&c<='9') { str+=c; while((cin.peek()>='0'&&cin.peek()<='9')||cin.peek()=='.') { c=cin.get(); str+=c; } str+=' '; } if(c=='+'||c=='-') { if(str.size()==0||(last=='+'||last=='-'||last=='*'||last=='/'||last=='(')) { if(c!='+') str+=c; } else { if(!sta.empty()&&(sta.top()=='*'||sta.top()=='/')) { while(!sta.empty()&&sta.top()!='(') { str+=sta.top(); str+=' '; sta.pop(); } } sta.push(c); } } if(c=='*'||c=='/') { sta.push(c); } if(c=='(')sta.push(c); if(c==')') { while(sta.top()!='(') { str+=sta.top(); str+=' '; sta.pop(); } sta.pop(); } last=c; } while(!sta.empty()) { str+=sta.top(); str+=' '; sta.pop(); } } void output() { for(int i=0;i!=str.size()-1;i++) { cout<<str[i]; } cout<<endl; } int main() { solve(); output(); return 0; }