栈的模拟应用:
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<cstdlib> #include<algorithm> #include<stack> using namespace std; string getPostfixExp(string s) { stack<char> sta;// d n x string exp; int len = s.size(); ; i<len; i++){ char ch = s[i]; if(ch == 'a' || ch == 'm') { //如果是字母 i += ; sta.push(s[i]); } else if(ch == '('){ sta.push(ch); } else if(ch == ')'){//此时顶一定是( sta.pop();//弹走( exp += " "; exp += sta.top(); sta.pop(); } else if(ch != ','){ //数字 string num; '){ num += s[i++]; } ] != NULL)//后缀表达式的第一个一定是数字,用此来避免首位空格 exp += " "; exp += num; i--; } } return exp; } int calculate(string post) { stack<int>sta; int len = post.size(); ; i<len; i++){ int ch = post[i]; if(ch >= 'a') {//如果是运算符 int a = sta.top(); sta.pop(); int b = sta.top(); sta.pop(); if(ch == 'd') sta.push(a+b); else if(ch == 'x') sta.push(max(a, b)); else if(ch == 'n') sta.push(min(a, b)); } else if(ch != ' ') {//如果为数字 ; ') num = num*+post[i++]-'; sta.push(num); i--; } } return sta.top(); } int main() { freopen("d:\\in.txt", "r", stdin); string s; int t; cin>>t; while(t--) { cin>>s; string post = getPostfixExp(s); cout<<calculate(post)<<endl; } ; }