224. Basic Calculator （hard ). !!!

Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().
 
Example 1:
Input: s = "1 + 1"
Output: 2
Example 2:
Input: s = " 2-1 + 2 "
Output: 3
Example 3:
Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23
 
Constraints:
1 <= s.length <= 3 * 105
s consists of digits, '+', '-', '(', ')', and ' '.
s represents a valid expression.
'+' is not used as a unary operation (i.e., "+1" and "+(2 + 3)" is invalid).
'-' could be used as a unary operation (i.e., "-1" and "-(2 + 3)" is valid).
There will be no two consecutive operators in the input.
Every number and running calculation will fit in a signed 32-bit integer.

A:
递归。

每当遇到了 ( ， 就去找到其对应的） ，然后里面包含的字符串就递归调用本身

class Solution {

public:

int calculate(string s) {

int res =0, start = 0;

vector<string> V;

while(start < s.size()){

if(s[start] == ' '){

start ++;

}else if(s[start] == '-' || s[start] == '+'){

V.push_back(s.substr(start,1));

start++;

}else if(s[start] == '('){

// find ending '('

int nDiff = 1; // count of ( - count of )

int end = start;

while(nDiff > 0 && end < s.size()){

end++; // Must increase here, bottom within while is wrong

if(s[end] == '('){

nDiff++;

}else if(s[end] == ')'){

nDiff--;

}

}

int val = calculate(s.substr(start+1, end- start-1));

start = end +1;

V.push_back(to_string(val));

}else if(isdigit(s[start]) ){

int end = start;

while(isdigit(s[end]) && end < s.size()){

end++;

}

V.push_back(s.substr(start, end-start));

start = end;

}

}

// need to check first .

start = 0;

if(V[0] != "-"){

res = stoi(V[0]);

start = 1;

}

for(int i =start; i<V.size(); i+= 2){

if(V[i]=="-"){

res -= stoi(V[i+1]);

}else{

res += stoi(V[i+1]);

}

}

return res;

}

};

Pass了，但是代价就是beat了不到10%

改进， 利用& 和 起止的index 作为参数传递给函数。 然而测试后并没有什么改善。可见消耗的时间更多的是在把n层的（）要跑n遍上。 

因此还是要用stack 呀

Error：

in C++,

         char ch = '-';

         std::cout<< std::to_string(ch);

会打印 45.  而不是"-"  

因为 std::to_string(ch) expects a number, not a character.

需要用Stack.  但是考虑到每个（）都是独立的，因此遇到（ 就是新的一层， 遇到）就计算并删掉最高的一层。     ---------》 只是最终结果也只是比上面好了一点点。 beat 10% 不到

class Solution {

public:

int calculate(string s) {

// use stack of vectors. when see ( go upper layer, and when see )

// calculate top layer, and append result to lower layer

stack<vector<string>> S;

S.push(vector<string>{}); // need make first layer

for (int i = 0; i < s.size(); i++) {

if (s[i] == '-' || s[i] == '+') {

S.top().push_back(s.substr(i, 1));

} else if (s[i] == '(') {

S.push(vector<string>{});

} else if (s[i] == ')') {

int val = helper(S.top());

S.pop();

S.top().push_back(to_string(val));

} else if (isdigit(s[i])) {

int end = i;

while (isdigit(s[end]) && end < s.size()) {

end++;

}

S.top().push_back(s.substr(i, end - i));

i = end - 1; // since we have i++ in the for loop

}

}

return helper(S.top());

}

private:

int

helper(const vector<string>& V) { // without (), calculate only += digits

int start = 0, res = 0;

if (V[0] != "-") { // first check if start with a number or -

res = stoi(V[0]);

start = 1;

}

for (int i = start; i < V.size(); i += 2) {

if (V[i] == "-") {

res -= stoi(V[i + 1]);

} else {

res += stoi(V[i + 1]);

}

}

return res;

}

};

**************错误就是出在每次都要substring上***************

别人的代码

public class Solution {
    public int calculate(String s) {
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(1);
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                int num = c - '0';
                int j = i + 1;
                while (j < s.length() && Character.isDigit(s.charAt(j))) {
                    num = 10 * num + (s.charAt(j) - '0');
                    j++;
                }
                res += stack.pop() * num;
                i = j - 1;
            } else if (c == '+' || c == '(') {
                stack.push(stack.peek());
            } else if (c == '-') {
                stack.push(-1 * stack.peek());
            } else if (c == ')') {
                stack.pop();
            }
        }
        return res;
    }
}

Mistakes:
1：  自己的解法有个最需要注意的问题就是：   pop完了（）两个运算符之后，要再 调用check（），因为我们相当于重新加入了一个运算数了



————————————————————————————————————
第一个解法，会造成某个数字是负数。再代入的话，就破坏原题目的简洁了
另外，  可能有多个括号并列的情况存在。