1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90
|
#include<cstring> #include<stack> #include<queue> using namespace std; const int N=200; char str[N],expr[N]; int n,len,idx[N],cnt=0; stack<char> opt; deque<int> num; deque<int>::iterator it; void () { idx['+']=idx['-']=1; idx['*']=idx['/']=2; idx['^']=3; } void trans() { for(int i=1;i<=len;i++) { if ('0'<=str[i]&&str[i]<='9') expr[++cnt]=str[i]; else { if (!idx[str[i]]) { if (str[i]=='(') opt.push(str[i]); if (str[i]==')') { while (opt.top()!='(') expr[++cnt]=opt.top(),opt.pop(); opt.pop(); } } else { while (!opt.empty()&&idx[opt.top()]>=idx[str[i]]) expr[++cnt]=opt.top(),opt.pop(); opt.push(str[i]); } } } while (!opt.empty()) expr[++cnt]=opt.top(),opt.pop(); } void print(int k) { for(it=num.begin();it!=num.end();it++) printf("%d%c",*it,k>cnt?'n':' '); for(int i=k;i<=cnt;i++) printf("%c%c",expr[i],i==cnt?'n':' '); } int pow(int a,int b) { int ret=1; while (b) { if (b&1) ret*=a; a*=a,b>>=1; } return ret; } int main() { init(); scanf("%s",str+1); len=strlen(str+1); trans(); print(1); for(int i=1;i<=cnt;i++) { if ('0'<=expr[i]&&expr[i]<='9') num.push_back(expr[i]-'0'); else { int b=num.back();num.pop_back(); int a=num.back();num.pop_back(); switch (expr[i]) { case '+':num.push_back(a+b);break; case '-':num.push_back(a-b);break; case '*':num.push_back(a*b);break; case '/':num.push_back(a/b);break; default:num.push_back(pow(a,b)); } print(i+1); } } return 0; }
|
近期评论