acmclub5904:
C++代码
1 #include<iostream>
2 #include<string>
3 #include<cctype>
4 #include<stack>
5 using namespace std;
6 struct node{
7 int data;
8 bool isnum;
9 node *lch,*rch;
10 };
11 int pri[127];
12 stack<node *> opd;
13 stack<node *> opr;
14 void create(node *&root,const string &s) //建数据栈 和 符号栈
15 {
16 int i,len;
17 node *p,*q,*r;
18 for (i=0,len=s.size();i<len;i++)
19 {
20 if (isdigit(s[i])) { //数据
21 p=new(node);
22 p->data=s[i]-'0'; p->isnum=true;
23 p->lch=p->rch=NULL;
24 opd.push(p);
25 continue;
26 }
27 if (s[i]=='(') { //左括号
28 p=new(node);
29 p->data=(int)s[i]; p->isnum=false;
30 p->lch=p->rch=NULL;
31 opr.push(p);
32 continue;
33 }
34 if (s[i]==')'){ //右括号，出到左括号与之配对
35 p=opr.top();
36 opr.pop();
37 while (p->data!=(int)'('){ //出到左括号与之配对
38 q=opd.top(); opd.pop(); p->rch=q; //出数据
39 q=opd.top(); opd.pop(); p->lch=q; //出数据
40 opd.push(p); //运算后再入数据栈
41 p=opr.top();
42 opr.pop();
43 }
44 continue;
45 }
46 //以下是其它运算符
47 p=new(node);
48 p->data=(int)s[i]; p->isnum =false;
49 p->lch=p->rch=NULL;
50
51 if (opr.empty()) { opr.push(p); continue; }
52 char ch=(char)(opr.top()->data) ;
53 if (ch=='('||pri[s[i]]>pri[ch]) { opr.push(p); continue; }
54
55 while (ch!='('&&pri[s[i]]<=pri[ch]) { //当前字符优先级低于栈顶字符，注意左括号
56 r=opr.top(); opr.pop();
57 q=opd.top(); opd.pop(); r->rch=q;
58 q=opd.top(); opd.pop(); r->lch=q;
59 opd.push(r);
60 if (opr.empty()) break;
61 ch=(char)(opr.top()->data) ;
62 }
63 opr.push(p);
64 }
65 while (!opr.empty())
66 {
67 p=opr.top(); opr.pop();
68 q=opd.top(); opd.pop(); p->rch=q;
69 q=opd.top(); opd.pop(); p->lch=q;
70 opd.push(p);
71 }
72 root=opd.top();
73 }
74 void deal(node *root)
75 {
76 char ch=root->data;
77 switch (ch)
78 {
79 case '+': root->data =root->lch->data + root->rch->data; break;
80 case '-': root->data =root->lch->data - root->rch->data; break;
81 case '*': root->data =root->lch->data * root->rch->data; break;
82 case '/': root->data =root->lch->data / root->rch->data; break;
83 case '^': int t=1;
84 for (int i=0;i<root->rch->data;i++)
85 t*=root->lch->data;
86 root->data =t;
87 break;
88 }
89 root->isnum =true;
90 root->lch = root->rch = NULL;
91 }
92 void lastord(node *root,bool &merged)
93 {
94 if (root) {
95 lastord(root->lch,merged);
96 lastord(root->rch,merged);
97 if (root->isnum)
98 cout<<root->data<<" ";
99 else cout<<(char)root->data<<" " ;
100 if (root->lch&&!merged){
101 deal(root);
102 merged=true;
103 }
104 }
105 }
106 int main()
107 {
108 pri['+']=1; pri['-']=1; pri['*']=2; pri['/']=2; pri['^']=3;
109 string s;
110 node *root;
111 cin>>s;
112 create(root,s);
113 bool merged;
114 while (root->lch){
115 merged=false;
116 lastord(root->lch,merged);
117 lastord(root->rch,merged);
118 cout<<(char)root->data<<endl; //左右根，这时根是运算符
119 if (root->lch&&!merged){ //最后一次运算merged在这里必然为假
120 deal(root);
121 merged=true;
122 }
123 }
124 cout<<root->data<<endl;
125 return 0;
126 }posted on 2014-04-02 19:49
龙在江湖 阅读(177)
评论(0) 编辑 收藏 引用 所属分类:
数据结构