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 .

• You may assume that the given expression is always valid.

Some examples:

"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

Solution

class Solution {
public:
    int help(string s) {
        // evaluate an expression without brackets
        // note the special case of ("2--1")
        int n = s.size();
        string tmp = "";
        int n1, res = 0, factor = 1;
        for ( int i = 0; i <= n-1; i++ ) {
            if ( s[i] == '+' or s[i] == '-') {
                if ( tmp != "" ) { 
                    n1 = stoi(tmp); 
                    res += n1*factor;
                    tmp = "";
                }
                factor = 2*(s[i] == '+') - 1;
                if ( s[i+1] == '-' ) { factor *= -1; i += 1; }
            }
            else tmp += s[i];
        }
        if ( tmp != "") res += stoi(tmp)*factor;
        return res;
    }
    int calculate(string s) {
        s = "(" + s + ")";
        int n = s.size();
        stack<string> record;
        for ( int i = 0; i <= n-1; i++ ) {
            if ( s[i] != ')' ) { record.push(s.substr(i, 1)); continue; }
            string tmp = "";
            while ( record.top() != "(" ) {
                tmp = record.top() + tmp;
                record.pop();
            }
            record.pop();
            record.push(to_string(help(tmp)));
        }
        return stoi(record.top());
    }
};

Notes

• Use the result from "Basic Calculator" to treat the slice of string without ().
• Note the special case of 2-(1-2) ( reduced to 2--1).

Notes-II
第二遍做好难做对，烦。