資訊專(zhuān)欄INFORMATION COLUMN
摘要：但是乘除就會(huì)有問(wèn)題，要特殊處理。這題只有加減和括號(hào)，優(yōu)先級(jí)就是括號(hào)里的先計(jì)算，所有我們把括號(hào)里的內(nèi)容當(dāng)做操作的基本單位。遇到遇到和，遇到遇到，彈出再遇到彈出，這里只是把對(duì)數(shù)字的操作變成了對(duì)的操作，去括號(hào)的邏輯一樣。
The expression string contains only non-negative integers, +, -, *, / operators and empty spaces. The integer division should truncate toward zero. "3+2*2" = 7 " 3/2 " = 1 " 3+5 / 2 " = 5
這題只有基本的四則運(yùn)算符號(hào)，不包含括號(hào)。模擬計(jì)算器的難點(diǎn)在于，運(yùn)算法則里符號(hào)有優(yōu)先級(jí)，先乘除后加減。 人類(lèi)的邏輯是先找到乘除的部分，多帶帶計(jì)算這些部分，變成整數(shù)，和加減一起運(yùn)算，代碼模擬起來(lái)麻煩且費(fèi)時(shí)。 按照從左到右的順序掃描，遇到加減直接運(yùn)算，不會(huì)出錯(cuò)。但是乘除就會(huì)有問(wèn)題，要特殊處理。 這里我們把上次遇到的數(shù)字存到stack里，如果遇到乘除符合，說(shuō)明上次操作不對(duì)，需要從結(jié)果里減去這個(gè)數(shù)字。 而且還可以得到乘數(shù)和除數(shù)是多少，進(jìn)行乘除部分的操作。
public class Solution {
public int calculate(String s) {
Stack stk = new Stack();
int res = 0, num = 0;
char lastSign = "+";
char[] cArray = s.toCharArray();
for(int i=0; i < cArray.length; i++){
char c = cArray[i];
if(c >= "0" && c <= "9"){
num = num*10 + c -"0";
}
if(c == "+" || c == "-" || c == "*" || c == "/" || i == cArray.length-1){
if(lastSign == "+" || lastSign == "-"){
int temp = lastSign == "+" ? num : -num;
stk.push(temp);
res += temp;
}
if(lastSign == "*" || lastSign == "/"){
res -= stk.peek();
int temp = lastSign == "*" ? stk.pop()*num : stk.pop()/num;
stk.push(temp);
res += temp;
}
lastSign = c;
num = 0;
}
}
return res;
}
}
224 Basic Calculator
The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces. "1 + 1" = 2 " 2-1 + 2 " = 3 "(1+(4+5+2)-3)+(6+8)" = 23
這題只有加減和括號(hào)，優(yōu)先級(jí)就是括號(hào)里的先計(jì)算，所有我們把括號(hào)里的內(nèi)容當(dāng)做操作的基本單位。
括號(hào)外的符號(hào)就當(dāng)做整體的符號(hào)，最后和括號(hào)外的同層數(shù)字進(jìn)行加減運(yùn)算。
比如 (2-(2+1))
初始化sign = 1, res =0;
stk{1,2,3,4,5} 簡(jiǎn)單表示stk最右的棧頂。
遇到(, stk{0, 1}, 遇到2和-， stk{0,1,2,-1}
遇到2+1 = 3, 遇到)， stk彈出res = 3*(-1) +2 = -1, stk{0,1}
再遇到), stk彈出，res = -1*1 + 0 = -1.
public class Solution {
public int calculate(String s) {
int sign = 1, result = 0;
Stack stk = new Stack();
char[] cArray = s.toCharArray();
for(int i=0; i< cArray.length; i++){
if(Character.isDigit(cArray[i])){
int num = 0;
while(i < cArray.length && Character.isDigit(cArray[i])){
num = 10*num + cArray[i] - "0";
i++;
}
i--;
result = result + sign*num;
} else if(cArray[i] == "+"){
sign = 1;
} else if(cArray[i] == "-"){
sign = -1;
} else if(cArray[i] == "("){
stk.push(result);
stk.push(sign);
result = 0;
sign = 1;
} else if(cArray[i] == ")"){
result = result*stk.pop() + stk.pop();
}
}
return result;
}
}
394 Decode String
The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. s = "3[a]2[bc]", return "aaabcbc". s = "3[a2[c]]", return "accaccacc". s = "2[abc]3[cd]ef", return "abcabccdcdcdef". 這里只是把對(duì)數(shù)字的操作變成了對(duì)str的操作，去括號(hào)的邏輯一樣。
public class Solution {
public String decodeString(String s) {
Stack numStk = new Stack<>();
Stack sbStk = new Stack<>();
int num = 0;
StringBuilder cur = new StringBuilder();
for(char c: s.toCharArray()){
if(c >= "0" && c <= "9"){
num = num*10 + c -"0";
} else if(c == "["){
numStk.push(num);
sbStk.push(cur);
num = 0;
cur = new StringBuilder();
} else if(c == "]"){
StringBuilder temp = cur;
cur = sbStk.pop();
for(int i = numStk.pop(); i > 0; i--) cur.append(temp);
} else {
cur.append(c);
}
}
return cur.toString();
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/66943.html
摘要：復(fù)雜度思路用兩個(gè)來(lái)分別記錄當(dāng)前的結(jié)果和操作符注意每一次統(tǒng)計(jì)當(dāng)前的的時(shí)候，要看一下下一位的操作符。有一種的方法，是表示的是匹配任意的空白符，包括空格，制表符，換行符，中文全角空格等。也可以用更簡(jiǎn)單的方法，。 LeetCode[227] Basic Calculator II Implement a basic calculator to evaluate a simple expres...
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...
摘要：題目鏈接，就是感覺(jué)條件有點(diǎn)多簡(jiǎn)單點(diǎn)的寫(xiě)法，把直接用存在里面，就存成，存成題目鏈接這題就是碰到在加減后面怎么處理的問(wèn)題。用一個(gè)來(lái)表示之前的，所以碰到現(xiàn)在是乘的時(shí)候就，除類(lèi)似。 224. Basic Calculator 題目鏈接：https://leetcode.com/problems... stack，就是感覺(jué)條件有點(diǎn)多 public class Solution { pub...
摘要：難點(diǎn)在于多了括號(hào)后如何處理正負(fù)號(hào)。但是每多一個(gè)括號(hào)，都要記錄下這個(gè)括號(hào)所屬的正負(fù)號(hào)，而每當(dāng)一個(gè)括號(hào)結(jié)束，我們還要知道出來(lái)以后所在的括號(hào)所屬的正負(fù)號(hào)。 Basic Calculator I 最新更新請(qǐng)見(jiàn): https://yanjia.li/zh/2019/01/... Implement a basic calculator to evaluate a simple express...
摘要：復(fù)雜度思路將字符串先轉(zhuǎn)換成后綴表達(dá)式，再將其出來(lái)。 Leetcode[224] Basic Calculator Implement a basic calculator to evaluate a simple expression string. The expression string may contain open ( and closing parentheses ),...
閱讀 1228·2023-04-25 20:56
閱讀 2278·2023-04-25 14:42
閱讀 1035·2023-04-25 14:06
閱讀 2874·2021-10-14 09:42
閱讀 2150·2021-09-22 16:03
閱讀 994·2021-09-13 10:30
閱讀 1352·2019-08-29 15:41
閱讀 1811·2019-08-29 12:55
