LeetCode:224.Basic Calculator

题目描述

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 .

Example 1:

Input: "1 + 1"
Output: 2

Example 2:

Input: " 2-1 + 2 "
Output: 3

Example 3:

Input: "(1+(4+5+2)-3)+(6+8)"
Output: 23

Note:

You may assume that the given expression is always valid.
Do not use the eval built-in library function.

解题思路 —— 递归求解

从左向右依次计算，当出现括号时，递归地优先计算括号内的算式。

AC 代码

class Solution {
public:
    int calculate(string s) {
        long long num = 0;
        char oper = '+';
        
        for(size_t i = 0; i < s.size(); ++i)
        { 
            if(s[i] >= '0' && s[i] <= '9')
            {
                long long curNum = 0;
                while(i < s.size() && s[i] >= '0' && s[i] <= '9')
                {
                    curNum = curNum*10 + s[i] - '0';
                    ++i;
                }
                --i;

                if(oper == '+') num += curNum;
                else if(oper == '-') num -= curNum;
            }
            else if(s[i] == '(') 
            {
                int j = i;
                int lc = 1;
                ++i;
                while(i < s.size() && lc != 0)
                {
                    if(s[i] == '(') ++lc;
                    else if(s[i] == ')') --lc;
                    ++i;
                }
    
                if(oper == '+') num += calculate(s.substr(j+1, i-j-2));
                else if(oper == '-') num -= calculate(s.substr(j+1, i-j-2));
                --i;
            }
            else if(s[i] == ' ')
            {
                continue;
            }
            else
            {
                oper = s[i];
            }
        }

        return num;
    }
};