当前位置:   article > 正文

C++Primer第五版 9.6节练习_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
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/花生_TL007/article/detail/178247
推荐阅读
相关标签
  

闽ICP备14008679号