basic_calculator.cpp

// 中缀表达式求职
// leetcode 224 题
// https://leetcode.com/problems/basic-calculator/
/*
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

示例 1：

输入：s = "1 + 1"
输出：2

示例 2：

输入：s = " 2-1 + 2 "
输出：3

示例 3：

输入：s = "(1+(4+5+2)-3)+(6+8)"
输出：23
*/
// 第一种解法
// 利用栈去梳理各运算的先后顺序, 将题目的输入处理成一个逆波兰表达式,然后从左往右,按顺序完成操作符和操作数的计算
class Solution1 {
public:
    int calculate(string s) {
        vector<string> tokens;
        stack<char> ops;
        long long val = 0;
        bool parsingNumber = false;;
        bool needs_zero = true;
        for (char ch : s) {
            if (ch >= '0' && ch <= '9') {
                val = val * 10 + ch - '0';
                parsingNumber = true;
                continue;
            }
            if (parsingNumber) {
                tokens.push_back(to_string(val));
                val = 0;
                parsingNumber = false;
                needs_zero = false;
            }
            if (ch == ' ') continue;
            if (ch == '(') {
                ops.push(ch);
                needs_zero = true;
                continue;
            }
            if (ch == ')') {
                while(ops.top()!= '(') {
                    tokens.push_back(string(1, ops.top()));
                    ops.pop();
                }
                ops.pop();
                needs_zero = false;
                continue;
            }
            if (needs_zero) tokens.push_back(to_string(0));
            while(
              !ops.empty() && 
              getRank(ops.top()) >= getRank(ch)) 
            {
                tokens.push_back(string(1, ops.top()));
                ops.pop();
            }
            ops.push(ch);
            needs_zero = true;
        }
        if (parsingNumber) tokens.push_back(to_string(val));
        while (!ops.empty()) {
            tokens.push_back(string(1, ops.top()));
            ops.pop();
        }
        return evalRPN(tokens);
    }

private:
    int getRank(char ch) {
        if (ch == '+' || ch == '-') return 1;
        if (ch == '*' || ch == '/') return 2;
        return 0;
    }
    int evalRPN(vector<string>& tokens) {
        stack<int> s;
        for(string token : tokens) {
            if (isOperator(token)) {
                int b = s.top();
                s.pop();
                int a = s.top();
                s.pop();
                s.push(calc(a, b, token));
            } else {
                s.push(stoi(token));
            }
        }
        return s.top();
    }

    int calc(int a, int b, string token) {
        if (token == "+") return a + b;
        if (token == "-") return a - b;
        if (token == "*") return a * b;
        if (token == "/") return a / b;
        return 0;
    }

    bool isOperator(string token) {
        return (
          token == "+" || 
          token == "-" ||
          token == "*" || 
          token == "/"
        );
    }
};

// 第二种解法
// 解释器设计模式
// 这两年 lowcode 或者no code都特别流行, 其实就是用一种相对简易的方式或指令去描述程序逻辑, 
// 然后平台代码去解析这些简易的描述,从而达到可以让一些非技术人员也能去通过平台来构建应用的目的.
// 那么回到这道题,我们也可以认为是,这一串字符串是一种相对简易的语言描述一组运算,我们可以通过解析器模式
// 去解析这段text, 推导出语法树,然后执行运算.

class Expression
{
public:
    virtual int interpret() = 0;
    virtual ~Expression() {};
};

class Number: public Expression
{

public:
    Number(string num) { this->number = atoi(num.c_str()); }
    ~Number() { }
    int interpret() { return number; }
private:
    int number;
};

class Plus : public Expression
{
public:
    Plus(Expression* left, Expression* right) :leftOperand(left), rightOperand(right) { }
    ~Plus() { delete leftOperand; delete rightOperand; }
    int interpret() { return leftOperand->interpret() + rightOperand->interpret(); }
private:
    Expression* leftOperand;
    Expression* rightOperand;
};

class Minus : public Expression
{
public:
    Minus(Expression* left, Expression* right) :leftOperand(left), rightOperand(right) { }
    ~Minus() { delete leftOperand; delete rightOperand; }
    int interpret() { return leftOperand->interpret() - rightOperand->interpret(); }
private:
    Expression* leftOperand;
    Expression* rightOperand;
};

class Multiply : public Expression
{
public:
    Multiply(Expression* left, Expression* right) :leftOperand(left), rightOperand(right) { }
    ~Multiply() { delete leftOperand; delete rightOperand; }
    int interpret() { return leftOperand->interpret() * rightOperand->interpret(); }
private:
    Expression* leftOperand;
    Expression* rightOperand;
};

class Divide : public Expression
{
public:
    Divide(Expression* left, Expression* right) :leftOperand(left), rightOperand(right) { }
    ~Divide() { delete leftOperand; delete rightOperand; }
    int interpret() { return leftOperand->interpret() / rightOperand->interpret(); }
private:
    Expression* leftOperand;
    Expression* rightOperand;
};

bool isOperator(const string &c) {
    return (c == "+" || c == "-" || c == "*" || c == "/" );
}
bool isOperator(const char &c) {
    return (c == '+' || c == '-' || c == '*' || c == '/');
}

class Evaluator : public Expression
{
private:
    Expression* syntaxTree;

public:
    Evaluator(vector<string>& s)
    {
        vector<Expression*> stack;
        for (unsigned int i=0; i < s.size(); i++) {
            if (isOperator(s[i])) {
                Expression* left  = stack.back(); stack.pop_back();
                Expression* right = stack.back(); stack.pop_back();
                switch(s[i][0]) {
                    case '+' :
                        stack.push_back(new Plus(right, left)); break;
                    case '-' :
                        stack.push_back(new Minus(right, left)); break;
                    case '*' :
                        stack.push_back(new Multiply(right, left)); break;
                    case '/' :
                        stack.push_back(new Divide(right, left)); break;
                }
            }else{
                stack.push_back(new Number(s[i]));
            }
        }
        syntaxTree = stack.back();
    }
    ~Evaluator() {
        delete syntaxTree;
    }

    int interpret() {
        return syntaxTree->interpret();
    }
};

class Solution2 {
public:
    int calculate(string s) {
        vector<string> exp = Parse(s);
        exp = Infix2RPN(exp);

        Evaluator sentence(exp);
        return sentence.interpret();
    }

private:
    int Priority(const string &c) {
        if (c == "*" || c == "/") {
            return 2;
        } else if (c== "+" || c == "-") {
            return 1;
        } else {
            return 0;
        }
    }

    vector<string> Infix2RPN(vector<string>& infix) {
        vector<string> rpn;
        stack<string> s;

        for(int i = 0; i < infix.size(); i++) {
            if(isdigit(infix[i][0])) {
                rpn.push_back(infix[i]);
            } else if (infix[i] == "(") {
                s.push(infix[i]);
            } else if (infix[i] == ")") {
                while(!s.empty() && s.top() != "(") {
                    rpn.push_back(s.top());
                    s.pop();
                }
                s.pop();
            }else if(isOperator(infix[i]) ){
                while(!s.empty() && Priority(s.top()) >= Priority(infix[i])) {
                    rpn.push_back(s.top());
                    s.pop();
                }
                s.push(infix[i]);
            }
        }
        while(!s.empty()) {
            rpn.push_back(s.top());
            s.pop();
        }
        return rpn;
    }
    vector<string> Parse(string& s){
        vector<string> exp;
        for(int i=0; i<s.size(); ){
            char c = s[i];
            string token;
            if (
                    c == '+' || c == '-' ||
                    c == '*' || c == '/' ||
                    c == '(' || c == ')'
                    ) {
                exp.push_back(token+c);
                i++;
                continue;
            }
            if ( isdigit(c) ) {
                while( isdigit(s[i]) ) {
                    token.push_back(s[i++]);
                }
                exp.push_back(token);
                continue;
            }
            i++;
        }
        return exp;
    }
};