實(shí)現(xiàn)一個(gè)基本的計(jì)算器來計(jì)算一個(gè)簡單的字符串表達(dá)式 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 由數(shù)字诬辈、'+'、'-'、'('搅吁、')'、和 ' ' 組成
s 表示一個(gè)有效的表達(dá)式
解題思路
1落午、這個(gè)只有加減法得計(jì)算谎懦，如果是'+' 號(hào)，不管有沒有括號(hào)都是一樣得板甘，如果是‘-’號(hào)党瓮，那么如果遇到括號(hào)里面得數(shù)字详炬，加號(hào)不變盐类，遇到‘-’ ，負(fù)負(fù)得正呛谜，所以要考慮這方便在跳，特別是多重括號(hào)，如果多重 ‘-’ 負(fù)號(hào)隐岛，怎么處理呢猫妙，可以把這些符號(hào)存到棧中，需要得時(shí)候一層層取出來聚凹，并且再一層層彈出
2割坠、獲取當(dāng)前得元素齐帚，i++ 是為了計(jì)算處下一個(gè)元素得位置
首先任何數(shù)x1=原來得數(shù)，可以當(dāng)符號(hào)使用彼哼，我們先壓入1对妄，當(dāng)遇到‘+’ ‘-’，取出當(dāng)前得棧頂元素重新賦值敢朱，假如 21-（-1+（-1））這個(gè)邏輯是怎么樣得
while循環(huán)剪菱，直接跳到數(shù)字階段，第二個(gè)while是為了取這種大于9得數(shù)字拴签，取值后計(jì)算num=21, ret=1*21=21
遇到'-'孝常，然后取出棧頂元素1，sign= -1
’（‘ 將 -1壓入棧蚓哩，
’-‘取出之前得棧頂值 -1 這個(gè)時(shí)候 變成正數(shù)构灸，然后后面進(jìn)行數(shù)字計(jì)算， num=1 ,ret=21+1=22,
然后是’+‘ 棧頂還是 sign= -1, 遇到’（‘ 繼續(xù)壓入一個(gè)數(shù)值-1岸梨，這個(gè)時(shí)候棧里面有2個(gè)數(shù)冻押，都是 -1，
然后’-‘ 這個(gè)時(shí)候sign=-(-1)=1, 運(yùn)算得時(shí)候 num=1 ret=22+1=23
然后')' 彈出棧頂?shù)玫谝粋€(gè)盛嘿，然后繼續(xù)彈出第二個(gè)
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;
}
}
知識(shí)點(diǎn)
1洛巢、雙向隊(duì)列Deque是double ended queue，將其理解成雙端結(jié)束的隊(duì)列次兆，雙端隊(duì)列稿茉，可以在首尾插入或刪除元素
和Queue的區(qū)別
Queue的解釋中，Queue就是簡單的FIFO隊(duì)列芥炭。
所以在概念上來說漓库，Queue是FIFO的單端隊(duì)列，Deque是雙端隊(duì)列
Deque<Integer> queue=new ArrayDeque<>();
Deque<Integer> stack=new LinkedList<>();
ArrayDeque: 基于數(shù)組實(shí)現(xiàn)的線性雙向隊(duì)列园蝠，通常作為椕燧铮或隊(duì)列使用，但是棧的效率不如LinkedList高彪薛。
LinkedList: 基于鏈表實(shí)現(xiàn)的鏈?zhǔn)诫p向隊(duì)列茂装，通常作為棧或隊(duì)列使用善延，但是隊(duì)列的效率不如ArrayQueue高少态。
2、
void push(int x) ----將元素 x 推到隊(duì)列的末尾
int pop()------------- 從隊(duì)列的開頭移除并返回元素
int peek()----------- 返回隊(duì)列開頭的元素易遣，返回堆棧頂部的元素
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
