LeetCode 772. Basic Calculator III题目解析-wowAC

Description

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -non-negative integers and empty spaces .

The expression string contains only non-negative integers, +-*/ operators , open ( and closing parentheses ) and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:

"1 + 1" = 2
" 6-4 / 2 " = 4
"2*(5+5*2)/3+(6/2+8)" = 21
"(2+6* 3+5- (3*14/7+2)*5)+3"=-12

 

Note: Do not use the eval built-in library function.

题目复述

题目的意思就是实现一个支持'+','-','*','/' ,'(',')'的计算器,题目保证输入的表达式是有效的,不能使用库。

题目解析

看到这个很自然的想起使用递归下降法来解决,get_token函数实现获取下一个记号(即 + –  * / ( )数字),文法只有三行:

exp := exp (+|-) additive | additive

additive := additive (*|/) factor | factor

factor := num | (exp)

照着文法写递归下降程序就可以了。此题有一个坑点,计算中间过程可能会爆int和long long,我们使用double来计算,注意执行除法运算后需要取整。

当然此题也可以用栈来实现,不过个人觉得递归下降程序更简洁,好控制。

class Solution {
public:
    string token;
    string str;
    int index;
    //找出下一个符号 + - * / ( ) 或者 数字
    string get_token() {
        while(str[index]==' ') index++;  //去除空格
        string token = "";
        if(index == str.length()) return token;
        switch(str[index]) {
            case '+':
                token += "+";
                index++;
                break;
            case '-':
                token += "-";
                index++;
                break;
            case '*':
                token += "*";
                index++;
                break;
            case '/':
                token += "/";
                index++;
                break;
            case '(':
                token += '(';
                index++;
                break;
            case ')':
                token += ')';
                index++;
                break;
            default: //数字
                while(str[index]>='0' && str[index]<='9') {
                    token += str[index];
                    index++;
                }
                break;
        }
        return token;
    }

    double exp() {
        double res = additive();
        while(token=="+" || token=="-") {
            string op = token;
            token = get_token();    //跳过'+' '-'
            if(op=="+") res += additive();
            else res -= additive();
        }
        return res;
    }
    double additive() {
        double res = factor();
        while(token=="*" || token=="/") {
            string op = token;
            token = get_token();   //跳过'*' '/'
            if(op == "*") res *= factor();
            else res = floor(res / factor());
        }
        return res;
    }
    double factor() {
        double res;
        if(token == "(") {
            token = get_token();
            res = exp();
            token = get_token();  //跳过')'
        }else {
            res = atoi(token.c_str());
            token = get_token();  //跳过num
        }
        return res;
    }
    int calculate(string s) {
        str = s;
        index = 0;
        token = get_token();
        return exp();
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注