摘要:但是乘除就會有問題,要特殊處理。這題只有加減和括號,優先級就是括號里的先計算,所有我們把括號里的內容當做操作的基本單位。遇到遇到和,遇到遇到,彈出再遇到彈出,這里只是把對數字的操作變成了對的操作,去括號的邏輯一樣。
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
這題只有基本的四則運算符號,不包含括號。模擬計算器的難點在于,運算法則里符號有優先級,先乘除后加減。 人類的邏輯是先找到乘除的部分,多帶帶計算這些部分,變成整數,和加減一起運算,代碼模擬起來麻煩且費時。 按照從左到右的順序掃描,遇到加減直接運算,不會出錯。但是乘除就會有問題,要特殊處理。 這里我們把上次遇到的數字存到stack里,如果遇到乘除符合,說明上次操作不對,需要從結果里減去這個數字。 而且還可以得到乘數和除數是多少,進行乘除部分的操作。
public class Solution { public int calculate(String s) { Stackstk = 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
這題只有加減和括號,優先級就是括號里的先計算,所有我們把括號里的內容當做操作的基本單位。 括號外的符號就當做整體的符號,最后和括號外的同層數字進行加減運算。 比如 (2-(2+1)) 初始化sign = 1, res =0; stk{1,2,3,4,5} 簡單表示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; Stackstk = 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". 這里只是把對數字的操作變成了對str的操作,去括號的邏輯一樣。
public class Solution { public String decodeString(String s) { StacknumStk = 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(); } }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/66943.html
摘要:復雜度思路用兩個來分別記錄當前的結果和操作符注意每一次統計當前的的時候,要看一下下一位的操作符。有一種的方法,是表示的是匹配任意的空白符,包括空格,制表符,換行符,中文全角空格等。也可以用更簡單的方法,。 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...
摘要:題目鏈接,就是感覺條件有點多簡單點的寫法,把直接用存在里面,就存成,存成題目鏈接這題就是碰到在加減后面怎么處理的問題。用一個來表示之前的,所以碰到現在是乘的時候就,除類似。 224. Basic Calculator 題目鏈接:https://leetcode.com/problems... stack,就是感覺條件有點多 public class Solution { pub...
摘要:難點在于多了括號后如何處理正負號。但是每多一個括號,都要記錄下這個括號所屬的正負號,而每當一個括號結束,我們還要知道出來以后所在的括號所屬的正負號。 Basic Calculator I 最新更新請見: https://yanjia.li/zh/2019/01/... Implement a basic calculator to evaluate a simple express...
摘要:復雜度思路將字符串先轉換成后綴表達式,再將其出來。 Leetcode[224] Basic Calculator Implement a basic calculator to evaluate a simple expression string. The expression string may contain open ( and closing parentheses ),...
閱讀 1216·2023-04-25 20:56
閱讀 2255·2023-04-25 14:42
閱讀 1020·2023-04-25 14:06
閱讀 2859·2021-10-14 09:42
閱讀 2136·2021-09-22 16:03
閱讀 978·2021-09-13 10:30
閱讀 1342·2019-08-29 15:41
閱讀 1789·2019-08-29 12:55