实现一个基本的计算器来计算一个简单的字符串表达式 s 的值。
示例 1：
输入：s = "1 + 1"
输出：2示例 2：
输入：s = " 2-1 + 2 "
输出：3示例 3：
输入：s = "(1+(4+5+2)-3)+(6+8)"
输出：23提示：
1 <= s.length <= 3 * 105
s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
s 表示一个有效的表达式
解题思路
1、这个只有加减法得计算，如果是'+' 号，不管有没有括号都是一样得，如果是‘-’号，那么如果遇到括号里面得数字，加号不变，遇到‘-’ ，负负得正，所以要考虑这方便，特别是多重括号，如果多重 ‘-’ 负号，怎么处理呢，可以把这些符号存到栈中，需要得时候一层层取出来，并且再一层层弹出
2、获取当前得元素，i++ 是为了计算处下一个元素得位置
首先任何数x1=原来得数，可以当符号使用，我们先压入1，当遇到‘+’ ‘-’，取出当前得栈顶元素重新赋值，假如 21-（-1+（-1））这个逻辑是怎么样得
while循环，直接跳到数字阶段，第二个while是为了取这种大于9得数字，取值后计算num=21, ret=1*21=21
遇到'-'，然后取出栈顶元素1，sign= -1
’（‘ 将 -1压入栈，
’-‘取出之前得栈顶值 -1 这个时候 变成正数，然后后面进行数字计算， num=1 ,ret=21+1=22,
然后是’+‘ 栈顶还是 sign= -1, 遇到’（‘ 继续压入一个数值-1，这个时候栈里面有2个数，都是 -1，
然后’-‘ 这个时候sign=-(-1)=1, 运算得时候 num=1 ret=22+1=23
然后')' 弹出栈顶得第一个，然后继续弹出第二个
class Solution {
public int calculate(String s) {
Deque<Integer> stack = new LinkedList();
stack.push(1);
int n=s.length();
int sign=1,i=0,ret=0;
while(i<n){
if(s.charAt(i)==' '){
i++;
}else if(s.charAt(i)=='+'){
sign=stack.peek();
i++;
}else if(s.charAt(i)=='-'){
sign=-stack.peek();
i++;
}else if(s.charAt(i)=='('){
stack.push(sign);
i++;
}else if(s.charAt(i)==')'){
stack.pop();
i++;
}else{
int num=0;
while(i<n&&Character.isDigit(s.charAt(i))){
num = 10 * num+s.charAt(i)- '0';
i++;
}
ret += sign * num;
}
}
return ret;
}
}
知识点
1、双向队列Deque是double ended queue，将其理解成双端结束的队列，双端队列，可以在首尾插入或删除元素
和Queue的区别
Queue的解释中，Queue就是简单的FIFO队列。
所以在概念上来说，Queue是FIFO的单端队列，Deque是双端队列
Deque<Integer> queue=new ArrayDeque<>();
Deque<Integer> stack=new LinkedList<>();
ArrayDeque: 基于数组实现的线性双向队列，通常作为栈或队列使用，但是栈的效率不如LinkedList高。
LinkedList: 基于链表实现的链式双向队列，通常作为栈或队列使用，但是队列的效率不如ArrayQueue高。
2、
void push(int x) ----将元素 x 推到队列的末尾
int pop()------------- 从队列的开头移除并返回元素
int peek()----------- 返回队列开头的元素，返回堆栈顶部的元素
Stack<String> STACK = new Stack<String>();
STACK.push("Welcome");
STACK.push("To");
STACK.push("Geeks");
STACK.push("For");
STACK.push("Geeks");
System.out.println(" stack is: " + STACK.peek());
stack is: Geeks
