算法表达式求值

叁歲伎倆 2022-05-27 10:26 240阅读 0赞

重中之重，这个博客还是有bug的，请转看逆波兰表达式(自认为当时写的还不错)

表达式求值中用到了两个栈，一个栈存放的是操作数，另一个栈存放的是操作符（运算符号和\#），\#可以让循环结束（\#优先级最小），下面是各个操作符优先级的比较，其中θ1为opter（操作符）栈的栈顶，θ2位字符ch，x意为不可比较

![20180417112053810][]

步骤：

1.先初始化两个栈opval（操作数）栈，opter（操作符）栈

2.将起始符\#压入opter栈中，以便后续循环中输入\#能够结束循环

3.定义一个count变量，并将初值设为0，这个变量的作用是能够将多位数字字符转化为double型压入栈中

4.循环（opter栈为空退出），内有两部分，一部分为数字的存放，另一部分为操作符的比较和存放，以及运算

①第一部分中分两类，一类实现的是多位数字的存入，另一类实现个位数字或第一次进入栈的单个数字字符的存入，同时这里就可以体现出count的作用了，具体实现看代码

②第二部分中使用到了两个函数，一个是返回二维数组下标的函数，另一个是返回优先级比较结果的函数

按照上表的顺序返回下标的函数中各个符号在数组中的位置是+~1，-~2，\*~3，/~4，（~5，）~6，\#~7

注意在优先级比较函数中，要减一（下标是从0开始的）

根据比较出来的结果：

如果是>，则将opval栈顶元素以及栈顶前面的一个元素弹出栈，最后将结果两数的计算结果存入栈中

如果是<，则直接将运算符压入opter栈中，接着读取字符

如果是=，则将opter栈顶元素弹出，接着读取字符

代码：

#include <iostream>
    #include <stack>
    #include <cctype>
    #include <cstdio>
    #include <cstdlib>
    using namespace std;
    
    stack <char> opter; //存储操作符
    stack <double> opval;   //存储操作数
    //根据上表返回操作符的位置下标
    int Index(char ch)
    {
        int index = 0;
        switch(ch)
        {
            case '+':
                index = 1;
                break;
            case '-':
                index = 2;
                break;
            case '*':
                index = 3;
                break;
            case '/':
                index = 4;
                break;
            case '(':
                index = 5;
                break;
            case ')':
                index = 6;
                break;
            case '#':
                index = 7;
                break;
            default:
                break;
        }
        return index;
    }
    //比较运算符之间的优先级
    char Compare(char ch1, char ch2)
    {
        char compare[][7] = {
                                {'>', '>', '<', '<', '<', '>', '>'},    //x表示不能比较
                                {'>', '>', '<', '<', '<', '>', '>'},
                                {'>', '>', '>', '>', '<', '>', '>'},
                                {'>', '>', '>', '>', '<', '>', '>'},
                                {'<', '<', '<', '<', '<', '=', 'x'},
                                {'>', '>', '>', '>', 'x', '>', '>'},
                                {'<', '<', '<', '<', '<', 'x', '='}
                            };
        int index1 = Index(ch1);
        int index2 = Index(ch2);
        return compare[index1 - 1][index2 - 1];
    }
    //计算
    double Calculate(char ch, double v1, double v2)
    {
        double v;
        switch(ch)
        {
            case '+':
                v = v1 + v2;
                break;
            case '-':
                v = v1 - v2;
                break;
            case '*':
                v = v1 * v2;
                break;
            case '/':
                v = v1 / v2;
                break;
            default:
                break;
        }
        return v;
    }
    //得到表达式的值
    double GetValue()
    {
        int count = 0;  //用来将多为数字存入栈中
        char ch;
        opter.push('#');
        ch = getchar();
        while(!opter.empty())   //操作符不为空是执行循环
        {
            if(isdigit(ch)) //isdigit若字符是数字，返回非0值
            {
                if(count == 1)  //count是1，说明数字是连续的
                {
                    double t = opval.top();    //将多位数字字符变为int型存放入栈中
                    opval.pop();
                    opval.push(t * 10 + ch - '0');
                }
                else    //数字第一次入栈或者数字是个位
                {
                    opval.push(ch - '0');
                    count = 1;
                }
                ch = getchar();
            }
            else    //字符是操作数
            {
                char c1, c2;
                double v1, v2;
                c1 = Compare(opter.top(), ch);
                switch(c1)
                {
                    case '<':
                        opter.push(ch);
                        ch = getchar();
                        break;
                    case '>':
                        c2 = opter.top();
                        opter.pop();
                        v2 = opval.top();
                        opval.pop();
                        v1 = opval.top();
                        opval.pop();
                        opval.push(Calculate(c2, v1, v2));
                        break;
                    case '=':
                        opter.pop();
                        ch = getchar();
                        break;
                    default:
                        cout << "输入有误，退出" << endl;
                        exit(0);
                        break;
                }
                count = 0;  //将其再次置位0
            }
        }
        return opval.top();
    }
    int main()
    {
        int n;
        cout << "你想要输入几次表达式:";
        cin >> n;
        getchar();
        while(n--)
        {
            cout << GetValue() << endl;
            opval.pop();    //将最后一个值弹出
        }
        return 0;
    }

运行结果：

![70][]

[20180417112053810]: /images/20220527/dc9c96b5d3ab496a86c05f5ccffe347c.png
[70]: /images/20220527/a8d63d5b8d224a25938275dceffa9b41.png