C++Primer第五版 9.6节练习_c++primer练习9.6

练习9.52：使用stack处理括号化的表达式。当你看到一个左括号，将其记录下来。当你在一个左括号之后看到一个右括号，从stack中pop对象，直至遇到右括号，将左括号也一起弹出栈。让后将一个值（括号内的运算结果）push到栈中，表示一个括号化的（子）表达式已经处理完毕，被其运算结果所替代。
答：见练习9.52.cpp
/*
*说明：函数说明
1.扫描表达式
a.如果 token 是 “+” ,”-“,”*”,”/”
a1.符号栈为空，token直接入栈
a2.符号栈不空，比较token和栈顶符号的优先级
如果token的优先级高，直接入栈
否则将栈里面的符号出栈，并和数字栈进行计算，设置新的栈顶符号和优先级，一直到优先级低的全部弹出栈，循环停止 ，新的符号入栈

b.如果 token是 “(“,直接入栈
c. 如果token是”)”
当stack_opt.top != “(“，既没有找到最近的和右括号匹配的左括号
操作符弹出栈，并和操作数计算
最后将”(“也弹出去
”）“不进栈，它的作用是为了消除掉最近的左括号） //循环外的pop是将左括号丢弃
d.剩下的情况就都是数字，直接进入操作数栈
*/

练习9.52（other’s）

/*
*练习9.52
*2015/8/8
*题目描述：练习9.52：使用stack处理括号化的表达式。当你看到一个左括号，将其记录下来。当你在一个左括号之后看到一个右括号，从stack中pop对象，直至遇到右括号，将左括号也一起弹出栈。让后将一个值（括号内的运算结果）push到栈中，表示一个括号化的（子）表达式已经处理完毕，被其运算结果所替代。 
*作者：海子
*参考网址：http://www.cnblogs.com/dolphin0520/p/3708602.html
*说明：时间做得太久，放弃，以后在弄 
*/

#include <iostream>
#include <vector>
#include <stack>
#include <string>
#include <cstdlib>
#include <cctype>
#include <cstring>
using namespace std;


vector<string> preParse(char *str)   //对中缀表达式进行预处理，分离出每个token
{
    vector<string> tokens;
    int len = strlen(str);
    char *p = (char *)malloc((len+1)*sizeof(char));  //注意不要用 char *p = (char *)malloc(sizeof(str))来申请空间
    int i=0,j=0;
    while(i<len)          //去除表达式中的空格
    {
        if(str[i]==' ')
        {
            i++;
            continue;
        }
        p[j++] = str[i++];
    }
    p[j]='\0';
    j=0;
    len = strlen(p);
    while(j<len)
    {
        char temp[2];
        string token;
        switch(p[j])
        {
            case '+':
            case '*':
            case '/':
            case '(':
            case ')':
                {
                    temp[0] =p[j];
                    temp[1] = '\0';
                    token=temp;
                    tokens.push_back(token);
                    break;
                }
            case '-':
                {
                    if(p[j-1]==')'||isdigit(p[j-1]))  //作为减号使用
                    {
                        temp[0] =p[j];
                        temp[1] = '\0';
                        token=temp;
                        tokens.push_back(token);
                    }
                    else    //作为负号使用
                    {
                        temp[0] ='#';
                        temp[1] = '\0';
                        token=temp;
                        tokens.push_back(token);
                    }  
                    break;
                }
            default:     //是数字
                {
                    i = j;
                    while(isdigit(p[i])&&i<len)
                    {
                        i++;
                    }
                    char *opd = (char *)malloc(i-j+1);
                    strncpy(opd,p+j,i-j);
                    opd[i-j]='\0';
                    token=opd;
                    tokens.push_back(token);
                    j=i-1;
                    free(opd);
                    break;
                }  
        }
        j++;
    }
    free(p);
    return tokens;
}



int getPriority(string opt)
{
    int priority;
    if(opt=="#")
        priority = 3;  
    else if(opt=="*"||opt=="/")
        priority = 2;
    else if(opt=="+"||opt=="-")
        priority = 1;
    else if(opt=="(")
        priority = 0;
    return priority;
}

void calculate(stack<int> &opdStack,string opt)
{
    if(opt=="#")  //进行负号运算
    {
        int opd = opdStack.top();
        int result = 0-opd;
        opdStack.pop();
        opdStack.push(result);
        cout<<"操作符:"<<opt<<" "<<"操作数:"<<opd<<endl; 
    }
    else if(opt=="+")
    {
        int rOpd = opdStack.top();
        opdStack.pop();
        int lOpd = opdStack.top();
        opdStack.pop();
        int result = lOpd + rOpd;
        opdStack.push(result); 

        cout<<"操作符:"<<opt<<" "<<"操作数:"<<lOpd<<" "<<rOpd<<endl; 
    }
    else if(opt=="-")
    {
        int rOpd = opdStack.top();
        opdStack.pop();
        int lOpd = opdStack.top();
        opdStack.pop();
        int result = lOpd - rOpd;
        opdStack.push(result); 
        cout<<"操作符:"<<opt<<" "<<"操作数:"<<lOpd<<" "<<rOpd<<endl; 
    }
    else if(opt=="*")
    {
        int rOpd = opdStack.top();
        opdStack.pop();
        int lOpd = opdStack.top();
        opdStack.pop();
        int result = lOpd * rOpd;
        opdStack.push(result); 
        cout<<"操作符:"<<opt<<" "<<"操作数:"<<lOpd<<" "<<rOpd<<endl; 
    }
    else if(opt=="/")
    {
        int rOpd = opdStack.top();
        opdStack.pop();
        int lOpd = opdStack.top();
        opdStack.pop();
        int result = lOpd / rOpd;
        opdStack.push(result); 
        cout<<"操作符:"<<opt<<" "<<"操作数:"<<lOpd<<" "<<rOpd<<endl; 
    }
}

int evaMidExpression(char *str)   //中缀表达式直接求值
{
    vector<string> tokens = preParse(str);
    int i=0;
    int size = tokens.size();

    stack<int> opdStack;     //存储操作数
    stack<string> optStack;   //存储操作符
    for(i=0;i<size;i++)
    {
        string token = tokens[i];
        if(token=="#"||token=="+"||token=="-"||token=="*"||token=="/")
        {
            if(optStack.size()==0)   //如果操作符栈为空
            {
                optStack.push(token);
            }
            else
            {
                int tokenPriority = getPriority(token);
                string topOpt = optStack.top();
                int topOptPriority = getPriority(topOpt);
                if(tokenPriority>topOptPriority)
                {
                    optStack.push(token);
                }
                else
                {
                    while(tokenPriority<=topOptPriority)
                    {
                        optStack.pop();
                        calculate(opdStack,topOpt);
                        if(optStack.size()>0)
                        {
                            topOpt = optStack.top();
                            topOptPriority = getPriority(topOpt);
                        }
                        else
                            break;

                    }
                    optStack.push(token);
                }
            }  
        }
        else if(token=="(")
        {
            optStack.push(token);
        }
        else if(token==")")
        {
            while(optStack.top()!="(")
            {
                string topOpt = optStack.top();
                calculate(opdStack,topOpt);
                optStack.pop();
            }
            optStack.pop();
        }
        else   //如果是操作数，直接入操作数栈
        {
            opdStack.push(atoi(token.c_str()));
        }
    }
    while(optStack.size()!=0)
    {
        string topOpt = optStack.top();
        calculate(opdStack,topOpt);
        optStack.pop();
    }
    return opdStack.top();
}


int main(int argc, char *argv[])
{
    char str[] = "((3+5*2)+3)/5+(-6)/4*2+3";
     vector<string> tokens = preParse(str);
     for(auto i = 0; i != tokens.size(); ++i)
     cout << tokens[i] << " ";
     cout << endl;
    cout<<evaMidExpression(str)<<endl;
    return 0;
}
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250

练习9.52（me）

/*
*练习9.52 
*2015/8/9
*问题描述： 练习9.52：使用stack处理括号化的表达式。当你看到一个左括号，将其记录下来。当你在一个左括号之后看到一个右括号，从stack中pop对象，直至遇到右括号，将左括号也一起弹出栈。让后将一个值（括号内的运算结果）push到栈中，表示一个括号化的（子）表达式已经处理完毕，被其运算结果所替代。 
*说明：自己模仿网上的写了一遍，熟悉了中缀 表达式计算的流程
*作者：NickFeng 
*邮箱：NickGreen23@163.com
*/ 

/*
*说明：
1.扫描表达式
  a.如果 token 是 "+" ,"-","*","/"
     a1.符号栈为空，直接入栈
     a2.符号栈不空，比较token和栈顶符号的优先级
        如果token的优先级高，直接入栈
        否则将栈里面的符号出栈，并和数字栈进行计算，设置新的栈顶符号和优先级，一直到优先级低的全部弹出栈，循环停止 ，新的符号入栈
  b.如果 token是 "(",直接入栈
  c. 如果token是")"
          当stack_opt.top != "("，既没有找到最近的和右括号匹配的左括号
          操作符弹出栈，并和操作数计算
          最后将"C"也弹出去
          ”）“不进栈，它的出现是为了消除掉最近的左括号） //循环外的pop是将左括号丢弃 
  d.剩下的情况就都是数字，直接进入操作数栈 
*/


#include <iostream>
#include <string>
#include <vector>
#include <stack>

using namespace std;

int priority(string opt)
{
    int p = 0;
    if(opt == "(")
        p = 1;
    if(opt == "+" || opt == "-")
        p = 2;
    if(opt == "*" || opt == "/")
        p = 3;
    return p;
}

void calculate(stack<int> &opdstack, string opt)
{
    if(opt == "+")
    {
        int ropd = opdstack.top();
        opdstack.pop();
        int lopd = opdstack.top();
        opdstack.pop();
        int result = lopd + ropd;
        opdstack.push(result);
    }
    if(opt == "-")
    {
        int ropd = opdstack.top();
        opdstack.pop();
        int lopd = opdstack.top();
        opdstack.pop();
        int result = lopd - ropd;
        opdstack.push(result);
    }
    if(opt == "*")
    {
        int ropd = opdstack.top();
        opdstack.pop();
        int lopd = opdstack.top();
        opdstack.pop();
        int result = lopd * ropd;
        opdstack.push(result);
    }
    if(opt == "/")
    {
        int ropd = opdstack.top();
        opdstack.pop();
        int lopd = opdstack.top();
        opdstack.pop();
        int result = lopd / ropd;
        opdstack.push(result);
    }
}



/*
*说明：
1.扫描表达式
  a.如果 token 是 "+" ,"-","*","/"
     a1.符号栈为空，直接入栈
     a2.符号栈不空，比较token和栈顶符号的优先级
        如果token的优先级高，直接入栈
        否则将栈里面的符号出栈，并和数字栈进行计算，设置新的栈顶符号和优先级，一直到优先级低的全部弹出栈，循环停止 ，新的符号入栈
  b.如果 token是 "(",直接入栈
  c. 如果token是")"
          当stack_opt.top != "("，既没有找到最近的和右括号匹配的左括号
          操作符弹出栈，并和操作数计算
          最后将"C"也弹出去
          ”）“不进栈，它的出现是为了消除掉最近的左括号） //循环外的pop是将左括号丢弃 
  d.剩下的情况就都是数字，直接进入操作数栈 
*/

int calcuExpression(vector<string> vec)
{
    stack<int> stack_opd;
    stack<string> stack_opt;

    for(auto i = 0; i != vec.size(); ++i)
    {
        string token = vec[i];
        if(token == "+" || token == "-" || token == "*" || token == "/")
        {
            if(stack_opt.size() == 0)
                stack_opt.push(token);
            else
             {
                int token_p = priority(token);
                string top_opt = stack_opt.top();
                int opt_p = priority(top_opt);
                if(token_p > opt_p)
                    stack_opt.push(token);
                else
                  {
                    while(token_p <= opt_p)
                    {
                        stack_opt.pop();
                        calculate(stack_opd, top_opt);
                        if(stack_opt.size() > 0)
                        {
                            top_opt = stack_opt.top();
                            opt_p = priority(top_opt);
                           }
                        else
                            break;
                      }
                      stack_opt.push(token);
                   }
             }
        }

        else if(token == "(")
            stack_opt.push(token);
        else if(token == ")")
        {
            while(stack_opt.top() != "(")
            {
                string top_opt = stack_opt.top();
                calculate(stack_opd,top_opt);
                stack_opt.pop();
            }
            stack_opt.pop();
        }
        else
          stack_opd.push(atoi(token.c_str()));  
    }

    while(stack_opt.size() != 0)
    {
        string top_opt = stack_opt.top();
        calculate(stack_opd,top_opt);
        stack_opt.pop();
    }
    return stack_opd.top();
}

int main()
{
    vector<string> tokens =  {"(","1","+","2",")","*","3","/","(","2","-","1",")"};


     for(auto i = 0; i != tokens.size(); ++i)
     cout << tokens[i] << " ";
     cout << endl;
     cout << calcuExpression(tokens) << endl;
    return 0;
}
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180

练习9.52（续）

/*
*练习9.52（续） 
*2015/8/9 
*说明：在练习9.52的基础上，将中缀表达式转化为后缀表达式进行计算，主要过程和9.52的几乎一样，但各个函数的功能更加明确（符数的情况没有考虑） 
*int priority() 符号的优先级 
*void shapeExpression(vector<string> vec);中缀表达式转后缀表达式
*int caculate();栈的计算过程
*int caclcuExpression()；后缀表达式的计算过程

*参考：海子 
*参考网址：http://www.cnblogs.com/dolphin0520/p/3708602.html
*作者：Nick Feng
*邮箱：nickgreen23@163.com  
*/

#include <iostream>
#include <vector>
#include <string>
#include <stack>

using namespace std;

int priority(string opt)
{
    int p = 0;
    if(opt == "+" || opt == "-")
        p = 1;
    if(opt == "*" || opt == "/")
        p = 2;
    if(opt == "(")
        p = 0;
    return p;
}

vector<string> shapeExpression(vector<string> &vec)
{
    stack<string> stack_opt;
    vector<string> vec2;

    for(auto i = 0; i != vec.size(); ++i)
    {
        string token = vec[i];
        if(token == "+" || token == "-" || token == "*" || token == "/")
        {
            if(stack_opt.size() == 0)
                stack_opt.push(token);
            else
            {
                int token_p = priority(token);
                string top_opt = stack_opt.top();
                int opt_p = priority(top_opt);
                if(token_p > opt_p)
                    stack_opt.push(token);
                else {
                    while(token_p <= opt_p)
                    {
                        //stack_opt.pop();
                        vec2.push_back(top_opt);
                        stack_opt.pop();
                        if(stack_opt.size() != 0)
                        {
                            top_opt = stack_opt.top();
                            opt_p = priority(top_opt);
                        }
                        else
                            break;
                    }
                    stack_opt.push(token);
                }
            }
        }
        else if(token == "(")
            stack_opt.push(token);
        else if(token == ")")
        {
            while(stack_opt.top() != "(")
            {
                string top_opt = stack_opt.top();
                vec2.push_back(top_opt);
                stack_opt.pop();
            }
            stack_opt.pop();
        }
        else 
        {
            vec2.push_back(token); 
        }
    }
    while(stack_opt.size() != 0)
    {
        string top_opt = stack_opt.top();
        vec2.push_back(top_opt);
        stack_opt.pop();
    }
    /*
    for(int i = 0; i != vec2.size(); ++i)
        cout << vec2[i] << " ";
        cout << endl;*/
        return vec2;
}


int calculate(stack<int> &stack_opd,string opt)
{
    if(opt == "+")
    {
        int ropd = stack_opd.top();
        stack_opd.pop();
        int lopd = stack_opd.top();
        stack_opd.pop();
        int result = lopd + ropd;
        stack_opd.push(result);
    }
    if(opt == "-")
    {
        int ropd = stack_opd.top();
        stack_opd.pop();
        int lopd = stack_opd.top();
        stack_opd.pop();
        int result = lopd - ropd;
        stack_opd.push(result);
    }
    if(opt == "*")
    {
        int ropd = stack_opd.top();
        stack_opd.pop();
        int lopd = stack_opd.top();
        stack_opd.pop();
        int result = lopd * ropd;
        stack_opd.push(result);
    }
    if(opt == "/")
    {
        int ropd = stack_opd.top();
        stack_opd.pop();
        int lopd = stack_opd.top();
        stack_opd.pop();
        int result = lopd / ropd;
        stack_opd.push(result);
    }
}

int calcuExpression(vector<string> vec)
{
    stack<int> stack_opd;
    //string s = "0123456789"
    for(int i = 0; i != vec.size(); ++i)
    {
        string token = vec[i];
        if(token == "+"|| token == "-" || token == "*" || token == "/")
            calculate(stack_opd,token);
        else
           stack_opd.push(atoi(token.c_str()));
    }
    return stack_opd.top();
}
int main()
{
    vector<string> v1 = {"(","1","+","2",")","*","4","/","(","1","+","1",")"};

    for(auto i = 0; i != v1.size(); ++i)
        cout << v1[i] << " ";
        cout << endl;

    vector<string> v2 = shapeExpression(v1);
    for(auto i = 0; i != v2.size(); ++i)
        cout << v2[i] << " ";
        cout << endl;

    cout << calcuExpression(v2) << endl;
    return 0;
}
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173