跳转至

数据结构——栈--计算器

学到栈这种数据结构，最经典最常见的练习就是用栈来计算逆波兰表达式。不过很让人疑惑的一点是，在LeetCode 150和一本通1198，都叫逆波兰表达式，但是形式完全不同。为了便于区分，根据运算符和数字的位置关系，将表达式分为三种表达式：前缀、中缀、后缀。

涉及的问题是：输入的三种表达式是否是有效的；三种表达式之间的相互转化（中缀转后缀，后缀转中缀等）；三种形式的表达式求值；

关注的问题：对于空格的处理，优先级（比如括号，指数运算符）的处理。

可以进行的扩展：与搜索和递归结合，比如LeetCode 282；进行表达式的展开，比如乘方展开等，就具体问题具体分析了。

上述问题处理好了，基本就是一个mini计算器。

把+-*/%^()这些运算符可以分为四类：

  • +-的优先级最低
  • */%高于加减运算
  • ^优先级高于前两类，并且是右结合的

  • ( )形成子表达式

  • 考虑运算式：a+b*c和a*b+c，读取运算数a，并立即把它写到后缀表达式中。下项是运算符+，问题是怎样处理+。我们在后缀表达式中没有第2个运算数，因此不能输出+，因为只有我们有了它的两个运算数之后，它才能出现在字符串中。解决办法是把运算符放在一个栈中，继续扫描。在我们发现了其右运算数后，运算符将会离开栈。读取运算数b，把它写入后缀表达式中。下一步我们发现了运算符*，其优先级高于+，因此在最终的后缀表达式中出现在+前面。把较低优先级运算符留在栈中，并把*添加到栈中。读取运算数c，把它写入后缀表达式中。完成了表达式的扫描后，清除栈并把运算符写到输出字符串中。结果为正确的后缀表达式：abc*+。同样的规律另一个中缀表达式转化成后缀表达式是ab*c+。

  • 考虑运算式a*b/c+d，读取前3项，把运算数a和b写入后缀字符串中，把运算符*放到栈中。字符串中的下一项是运算符/，它与*有相同的优先级。立即把/放入栈将会“掩埋”*，最终导致在后缀字符串中把/放到*的前面。这违背了运算符的左结合规则。我们必须扩展栈处理的概念。当扫描运算符时，先删除栈中与当前运算符优先级相同或较高的所有运算符，并把它们写到后缀字符串中。只有这时，我们才能把新运算符入栈。处理了运算数c之后，扫描过程读取运算符+。把+加入栈之前，删除（出栈）优先级较高的*，把它写到后缀表达式中。以运算数d结束扫描，然后从栈中删除运算符+。
  • 考虑运算式a^b^c，运算符是右结合的，即必须先计算表达式bc，把结果作为a的右运算数。关键是处理第2个运算符。读取符号ab后，运算数a和b位于后缀字符串中，运算符位于栈中。下一步必须处理第2个运算符。我们前面提出了条规则：输入的运算符在从栈中删除所有相同或较高优先级的运算符之后才能进入栈。因此如果输入的运算符和栈中的运算符有相同的优先级，则先把运算符出栈并写入后缀字符串中，这将产生表达式ab^。然后把第2个运算符放入栈，继续扫描，最后的后缀表达式为ab^c^。这违背了运算符的右结合规则。为了解决这个问题，我们采用一个新的策略：当运算符是右结合时，给它赋两个不同的优先级数值，输入优先级和栈优先级。当运算符位于栈中时，应用栈优先级。当我们读取一个运算符时，比较此运算符的输入优先级和栈顶部运算符的栈优先级。如果输入优先级低于或等于运算符的栈优先级，将运算符出栈并写入后缀字符串中。对栈中每个后面的运算符重复这个过程。如果输入优先级较高，则把运算符入栈。所以此运算式的转化结果为abc^^。
  • 考虑运算式a*(b+c)，当读取左圆括号时，就进入了子表达式，我们处理此了表达式就像处理平常的中缀表达式一样。主要的区别在于，子表达式在输入相应的右圆括号处中断。我们把左圆括号存储在栈中，直到遇到子表达式的结尾。因为**左圆括号开始新的子表达式，所以当前栈中的所有运算符必须保留在栈中**。我们通过给左圆括号提供低于任何运算符栈优先级的输入优先级来实现上面的要求。一旦(运算符位于栈中子表达式中，就没有运算符能够删除它，直到找到相应的右圆括号。我们通过把左圆括号的栈优先级定为-1，低于任何运算符的输入优先级，来确保它稳固地保留在栈中。一旦读取相应的右圆括号，就拥有了完整的子表达式，能够使栈中左圆括号后面的所有运算符出栈，并把它们写入后缀字符串中。通过从栈中删除左圆括号来结束子表达式的处理，然后继续扫描剩下的表达式。转化后的结果是abc+*。

通过上面四个例子才可以得到下面这种运算符优先级赋值的表格，除了括号运算符，其他运算符都是二元运算符，为了便于检查输入的中缀表达式是否正确，我们通过RANK值来进行评判。初始时rank = 0，每读取一个运算数，RANK值+1，遇到一个二元 运算符，那么显然需要第二个运算数，所以令二元运算数的RANK值为-1。运算符)的栈优先级为0，低于其他二元运算符的优先级，也就是直到遇到(，会一直弹出栈内运算符。由于(和)都不是二元运算符，所以其RANK值设为0。

所以如果中缀表达式输入正确，那么RANK值只能是0或1。如果是2，那么说明输入的数字过多，如果是-1，说明运算符输入不正确。（一般题目会保证输入的算式是正确的）。

符号 输入优先级 栈优先级 Rank
+ - 1 1 -1
* / % 2 2 -1
^ 4 3 -1
( 5 -1 0
) 0 0 0

通过分析总结出中缀表达式转后缀表达式需要遵循以下规则：

  • 在每个符号后面检查RANK值，其值必须是0或1。如果值为负，说明表达式的运算符太多。如果值为2，则说明表达式有太多的运算数。RANK最终值必须是1。

  • 如果输入是运算数，则立即把它写入后缀字符串中

  • 遇到运算符和左圆括号的输入，比较其输入优先级和栈中最上面项的栈优先级。如果栈优先级高于或等于输入优先级，运算符出栈，并写入后缀字符串中。继续这个过程，直到栈优先级不再高于或等于输入优先级。然后把输入符号入栈。
  • 如果输入是右圆括号，则说明扫描到了子表达式的结束。把栈中相应的左圆括号后面的所有运算符出栈，写入到后缀字符串中。然后出栈左圆括号，继续扫描过程
  • 到达中缀表达式的结尾后，出栈所有剩余的运算符，写入后缀字符串中

我们设计一个名为expressionSymbol的类来封装输入优先级和栈优先级的信息，并通过重载>=来对决定扫描到的运算符是否入栈及相应操作。

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

using namespace std;

const char lParen  = '(', rParen = ')';

class expressionSymbol
{
friend bool operator>= (const expressionSymbol& left, const expressionSymbol& right);

private:
    char op; //扫描到的运算符
    int inputPrecedence; //运算符的输入优先级
    int stackPrecedence; //运算符的输出优先级

public:
    expressionSymbol() {}

    expressionSymbol(char ch)
    {
        op = ch;   

        switch(op) {
            // '+' 和 '-' 输入/栈优先级 1
            case '+':   
            case '-': inputPrecedence = 1;
                       stackPrecedence = 1;
                      break;

            // '*', '%', '/' 输入/栈优先级 2
            case '*':   
            case '%':   
            case '/': inputPrecedence = 2;
                      stackPrecedence = 2;
                      break;

            // '^' is right associative. input precedence 4
            // and stack precedence 3
            case '^': inputPrecedence = 4;
                      stackPrecedence = 3;
                      break;

            // '(' has input precendence 5, stack precedence -1
            case '(': inputPrecedence = 5;
                      stackPrecedence = -1;
                      break;

            // ')' has input/stack precedence 0
            case ')': inputPrecedence = 0;
                      stackPrecedence = 0;
                      break;
        }
    }

    ~expressionSymbol() {}

    char getOp() const
    {
        return op;
    }

};

bool operator>= (const expressionSymbol& left, const expressionSymbol& right )
{
    return left.stackPrecedence >= right.inputPrecedence;
}

再设计一个名为infix2Postfix的类，将我们输入的中缀表达式字符串转换成后缀表达式并以字符串形式返回，输入的字符串可以包含空格，其他运算符则视为非法，同时检查输入的表达式是否正确。

class infix2Postfix
{
private:
    string infixExpression; //中缀表达式字符串
    string postfixExpression; //转换后的后缀表达式字符串
    stack<expressionSymbol> operatorStack; //用来存储扫描到的运算符

    //在输入的运算符入栈前把较高或相同优先级的运算符写入后缀表达式
    void outputHigherOrEqual(const expressionSymbol & op)
    {
        expressionSymbol op2;

        //栈非空且栈顶符号的栈优先级高于扫描到的运算符的输入优先级
        while(!operatorStack.empty() && (op2 = operatorStack.top()) >= op) {
            operatorStack.pop();
            postfixExpression += op2.getOp();
            postfixExpression += ' ';
        }
    }

    bool isOperator(char ch) const
    {
        return ch == '+' || ch == '-' || ch == '*' || ch == '%' || ch == '/' || ch == '^';
    }   

public:
    infix2Postfix(){}

    infix2Postfix(const string & infixExp): infixExpression(infixExp) {}

    void setInfixExp(const string & infixExp)
    {
        infixExpression = infixExp;
        postfixExpression = "";
    }

    string postfix();

    ~infix2Postfix() {}

};

string infix2Postfix::postfix()
{
    expressionSymbol op;
    int rank = 0;

    for (size_t i = 0; i < infixExpression.size(); ++i) {
        char ch = infixExpression[i];

        if (isdigit(ch)) {
            postfixExpression += ch;
            postfixExpression += ' ';
            rank++;
            if (rank > 1) cout << "infix2Postfix: Operator expected" << endl;
        }
        else if (isOperator(ch) || ch == '(') {
            if (ch != '(') rank--;

            if (rank < 0)
                cout << "infix2Postfix: Operand expected" << endl;  
            else {
                op = expressionSymbol(ch);
                outputHigherOrEqual(op);
                operatorStack.push(op);
            }
        }
        else if (ch == rParen) {
            op = expressionSymbol(ch);
            outputHigherOrEqual(op);
            if(operatorStack.empty())
                cout << "infix2Postfix: Missing '('" << endl;
            else
                operatorStack.pop(); // 删掉'('
        }
        else if (!isspace(ch))
            cout << "infix2Postfix: Invalid input" << endl;
    }

    if (rank != 1)
        cout << "infix2Postfix: Operand expected" << endl;
    else {
        while (!operatorStack.empty()) {
            op = operatorStack.top();
            operatorStack.pop();
            if (op.getOp() == lParen)
                cout << "infix2Postfix: Missing ')'" << endl;
            else {
                postfixExpression += op.getOp();
                postfixExpression += ' ';
            }
        }
    }

    return postfixExpression;
}

我们得到了一个后缀表达式字符串，设计一个名为postfixEval的类来计算出表达式的结果。计算过程中考虑/和%的右运算数为0的情形，以及不能出现0^0的表达式。

class postfixEval
{
private:
    string postfixExpression; //需要计算的后缀表达式字符串
    stack<int> operandStack; //一个栈用来存储运算符

    void getOperands(int & left, int & right)
    {
        if (operandStack.empty())
            cout << "postfixEval: Too many operators" << endl;

        right = operandStack.top();
        operandStack.pop();

        if (operandStack.empty())
            cout << "postfixEval: Too many operators" << endl;

        left = operandStack.top();
        operandStack.pop();
    }

    //计算表达式结果   
    int compute(int left, int right, char op) const
    {
        int value = 0;

        switch(op) {
            case '+':   value = left + right;
                        break;

            case '-':   value = left - right;
                        break;

            case '*':   value = left * right;
                        break;

            case '%':   if (right == 0) cout << "postfixEval: divide by 0" << endl;
                        else value = left % right;
                        break;

            case '/':   if (right == 0) cout << "postfixEval: divide by 0" << endl;
                        else value = left / right;
                        break;

            case '^':   if (left == 0 && right == 0) cout << "postfixEval: 0^0 undefined" << endl;
                        else {
                            value = 1;
                            while (right--) value *= left;                          
                        }
                        break;
        }

        return value;
    }

    bool isOperator(char ch) const
    {
        return ch == '+' || ch == '-' || ch == '*' || ch == '%' || ch == '/' || ch == '^';
    }

public:
    postfixEval() {}

    string getPostfixExp() const
    {
        return postfixExpression;
    }

    //初始化后缀表达式  
    void setPostfixExp(const string & postfixExp)
    {
        postfixExpression = postfixExp;
    }

    int evaluate()
    {
        int left, right;

        for (size_t i = 0; i < postfixExpression.size(); ++i)
        {
            char ch = postfixExpression[i];

            if (isdigit(ch))
                operandStack.push(ch - '0');
            else if (isOperator(ch)) {
                getOperands(left, right);
                operandStack.push(compute(left, right, ch));
            }
            else if (!isspace(ch)) cout << "postfixEval: Improper char" << endl;
        }

        int expValue = operandStack.top();
        operandStack.pop();

        if (!operandStack.empty()) cout << "postfixEval: Too many operands" << endl;

        return expValue;
    }

    ~postfixEval() {}
};

下面用一个写一个简单的测试程序：

int main()
{
    infix2Postfix iexp; //iexp进行从中缀到后缀的转换
    string infixExp, postfixExp; //中缀表达式输入和输出
    postfixEval pexp;

    cout << "Enter an infix expresion: " << endl;
    getline(cin, infixExp);
    cout << infixExp << endl;

    iexp.setInfixExp(infixExp);
    postfixExp = iexp.postfix(); //完成到后缀表达式的转换
    cout << postfixExp << endl;
    pexp.setPostfixExp(postfixExp);
    cout << pexp.evaluate() << endl; //输出计算结果

    return 0;
}

$ Enter an infix expresion: 
3 ^ 2 ^ (1  + 2 )
3 2 1 2 + ^ ^ 
6561

注意洛谷P1175 的测试数据其实未考虑乘方运算是右结合的（比如2^3^4），还是书中考虑的更为全面。这个程序基本把leetcode这几个题目可能遇到的问题都解决了。

典型题目

（282的题目和洛谷上P1874 快速求和类型相似，这道题可以和洛谷上的题目结合来进一步拓展，比如282可以拓展成如果可以通过加入表达式来使其得到目标值，那么最少加入多少个运算符？如果题目里允许加入括号282这道题答案又是什么？如果我要统计运算次数，乘法按照执行多少次加法来计算，最少需要多少次计算得到目标值？如果乘法记为一次运算，不能加入括号，那么只需要从282题目的结果里选出长度最小的，用它的长度减去未加入运算符的长度，就是需要加入的最少运算符号）

这几道题目本质都是计算器的设计，实际上就是将中缀表达式转成后缀表达式的各种变形。归结为以下几个问题：

  • 中缀表达式如何转化成后缀表达式
  • 输入的中缀/后缀表达式里空格等额外信息如何处理
  • 如何判断输入的中缀/后缀表达式是否正确
  • 符号计算问题（表达式求值、等价表达式）
  • 数字组成的字符串加入运算符类型的问题

虽然在《数据结构C++语言描述——应用标准库STL》里第六章里写到了，不过它的方法更像是去写一个小的模块，对于单独问题的理解

涉及的计算主要是：加减乘除，幂运算(或者leetcode实现pow()函数)，包含括号的优先级问题，快速阶乘，高精度，大数运算，多项式结合起来。

对于幂运算其实可以单独拉出来一个专题：快速幂。

对于本题，其实应该解决的第一问题就是“如何将前缀表达式转成后缀表达式”，可以参考洛谷 P1175 表达式的转换

150.Evaluate Reverse Polish Notation 相当于已经转成了逆波兰表达式，只需要利用一个栈计算即可。

额外补充的有P1739 表达式括号匹配（和leetcode20.Valid Parentheses类似）

P1449 后缀表达式

P1981 表达式求值

P1054 等价表达式（相当于符号计算）类似的有P2379 整式的计算

  • 一本通-1198：逆波兰表达式（递归，计算前缀表达式）
  • LeetCode 150 Evaluate Reverse Polish Notation (栈，计算后缀表达式)
  • LeetCode 224 Basic Calculator
  • LeetCode 227 Basic Calculator II
  • LeetCode 772 Basic Calculator III
  • LeetCode 770 Basic Calculator IV
  • LeetCode 991 Broken Calculator(这个和计算器设计差别较大，只是题目背景类似)
  • LeetCode上282 Expression Add Operators，（和UVA 817According to Bartjens其实是一个题目）
  • ​