摘要:難點在于多了括號后如何處理正負號。但是每多一個括號,都要記錄下這個括號所屬的正負號,而每當一個括號結束,我們還要知道出來以后所在的括號所屬的正負號。
Basic Calculator I 最新更新請見: https://yanjia.li/zh/2019/01/...
</>復制代碼
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
Note: Do not use the eval built-in library function.
棧法
復雜度
時間 O(N) 空間 O(N)
思路很多人將該題轉換為后綴表達式后(逆波蘭表達式)求解,其實不用那么復雜。題目條件說明只有加減法和括號,由于加減法是相同順序的,我們大可以直接把所有數順序計算。難點在于多了括號后如何處理正負號。我們想象一下如果沒有括號這題該怎們做:因為只有加減號,我們可以用一個變量sign來記錄上一次的符號是加還是減,這樣把每次讀到的數字乘以這個sign就可以加到總的結果中了。有了括號后,整個括號內的東西可一看成一個東西,這些括號內的東西都會受到括號所在區域內的正負號影響(比如括號前面是個負號,然后括號所屬的括號前面也是個負號,那該括號的符號就是正號)。但是每多一個括號,都要記錄下這個括號所屬的正負號,而每當一個括號結束,我們還要知道出來以后所在的括號所屬的正負號。根據這個性質,我們可以使用一個棧,來記錄這些括號所屬的正負號。這樣我們每遇到一個數,都可以根據當前符號,和所屬括號的符號,計算其真實值。
注意先用String.replace()去掉所有的空格
代碼</>復制代碼
public class Solution {
public int calculate(String s) {
// 去掉所有空格
s = s.replace(" ", "");
Stack stk = new Stack();
// 先壓入一個1進棧,可以理解為有個大括號在最外面
stk.push(1);
int i = 0, res = 0, sign = 1;
while(i < s.length()){
char c = s.charAt(i);
// 遇到正號,將當前的符號變為正號
if(c=="+"){
sign = 1;
i++;
// 遇到負號,將當前的符號變為負號
} else if(c=="-"){
sign = -1;
i++;
// 遇到左括號,計算當前所屬的符號,壓入棧中
// 計算方法是當前符號乘以當前所屬括號的符號
} else if(c=="("){
stk.push(sign * stk.peek());
sign = 1;
i++;
// 遇到右括號,當前括號結束,出棧
} else if(c==")"){
stk.pop();
i++;
// 遇到數字,計算其正負號并加入總結果中
} else {
int num = 0;
while(i < s.length() && Character.isDigit(s.charAt(i))){
num = num * 10 + s.charAt(i) - "0";
i++;
}
res += num * sign * stk.peek();
}
}
return res;
}
}
Basic Calculator II
棧法
復雜度
時間 O(N) 空間 O(N)
思路因為乘法和除法不僅要知道下一個數,也要知道上一個數。所以我們用一個棧把上次的數存起來,遇到加減法就直接將數字壓入棧中,遇到乘除法就把棧頂拿出來乘或除一下新數,再壓回去。最后我們把棧里所有數加起來就行了。
注意先用String.replace()去掉所有的空格
代碼</>復制代碼
public class Solution {
public int calculate(String s) {
s = s.replace(" ", "");
Stack stk = new Stack();
String firstNum = getNum(0, s);
stk.push(Long.parseLong(firstNum));
int i = firstNum.length();
while(i < s.length()){
char c = s.charAt(i);
// 拿出下一個數字
String numStr = getNum(i + 1, s);
if(c == "+"){
stk.push(Long.parseLong(numStr));
}
if(c == "-"){
stk.push(-Long.parseLong(numStr));
}
if(c == "*"){
stk.push(stk.pop()*Long.parseLong(numStr));
}
if(c == "/"){
stk.push(stk.pop()/Long.parseLong(numStr));
}
i = i+ numStr.length() + 1;
}
long res = 0;
while(!stk.isEmpty()){
res += stk.pop();
}
return (int)res;
}
private String getNum(int i, String s){
StringBuilder num = new StringBuilder();
while(i < s.length() && Character.isDigit(s.charAt(i))){
num.append(s.charAt(i));
i++;
}
return num.toString();
}
}
臨時變量法
復雜度
時間 O(N) 空間 O(1)
思路這題很像Expression Add Operator。因為沒有括號,其實我們也可以不用棧。首先維護一個當前的結果,加減法的時候,直接把下一個數加上或減去就行了。乘除法的技巧在于,記錄下上次的數字,這樣我們把上次計算出的結果,減去上次的數字,得到了上上次的結果,就相當于回退到加或減上一個數字之前的情況了。這時候我們再把上一個數字乘上或除以當前的數字,最后再加或減回上上次的結果,就是這次的結果了。比如2+3*4,當算完3時,結果是5,當算到4時,先用5-3=2,再用2+3*4=14,就是當前結果。這里要注意的是,對于下一個數,它的上一個數不是我們這輪的數,而是我們這輪的上輪的數乘以或除以這輪的數,如2+3*4*5,到4的時候結果14,到5的時候,上一個數是3*4,而不是4。
注意要多帶帶處理第一個數的情況
代碼</>復制代碼
public class Solution {
public int calculate(String s) {
s = s.replace(" ","");
long currRes = 0, prevNum = 0;
// 拿出第一個數
String firstNum = getNum(0, s);
currRes = Long.parseLong(firstNum);
prevNum = currRes;
int i = firstNum.length();
while(i < s.length()){
char c = s.charAt(i);
String numStr = getNum(i + 1, s);
System.out.println(numStr);
long n = Long.parseLong(numStr);
if(c == "+"){
currRes += n;
prevNum = n;
}
if(c == "-"){
currRes -= n;
prevNum = -n;
}
if(c == "*"){
// 上次的結果,減去上次的數,再加上上次的數乘以這次的數,就是這次的結果
currRes = currRes - prevNum + prevNum * n;
prevNum = prevNum * n;
}
if(c == "/"){
// 上次的結果,減去上次的數,再加上上次的數除以這次的數,就是這次的結果
currRes = currRes - prevNum + prevNum / n;
prevNum = prevNum / n;
}
// 計算完后,跳過當前的運算符和數字
i = i + numStr.length() + 1;
}
return (int)currRes;
}
private String getNum(int i, String s){
StringBuilder num = new StringBuilder();
while(i < s.length() && Character.isDigit(s.charAt(i))){
num.append(s.charAt(i));
i++;
}
return num.toString();
}
}
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://m.specialneedsforspecialkids.com/yun/64603.html
摘要:復雜度思路用兩個來分別記錄當前的結果和操作符注意每一次統計當前的的時候,要看一下下一位的操作符。有一種的方法,是表示的是匹配任意的空白符,包括空格,制表符,換行符,中文全角空格等。也可以用更簡單的方法,。 LeetCode[227] Basic Calculator II Implement a basic calculator to evaluate a simple expres...
摘要:題目中也給出了例子。因為沒有更高優先級的運算符,因此一旦我們遇到連續的形式,就可以立刻計算出結果。目前的想法是,一旦遇到括號,就將括號內的內容作為一個新的起點進行計算,但是括號前的內容也就是括號所位于的上下文需要通過棧來記錄。 題目要求 Implement a basic calculator to evaluate a simple expression string. The e...
摘要:雙棧法四則運算括號復雜度時間空間思路算符優先算法,核心維護兩個棧,一個操作數棧,一個操作符棧。 Basic Calculator 2 Implement a basic calculator to evaluate a simple expression string. The expression string contains only non-negative integers...
摘要:復雜度思路將字符串先轉換成后綴表達式,再將其出來。 Leetcode[224] Basic Calculator Implement a basic calculator to evaluate a simple expression string. The expression string may contain open ( and closing parentheses ),...
Problem Implement a basic calculator to evaluate a simple expression string. The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division sho...
閱讀 721·2021-11-16 11:44
閱讀 3552·2019-08-26 12:13
閱讀 3246·2019-08-26 10:46
閱讀 2362·2019-08-23 12:37
閱讀 1193·2019-08-22 18:30
閱讀 2538·2019-08-22 17:30
閱讀 1845·2019-08-22 17:26
閱讀 2296·2019-08-22 16:20