資訊專欄INFORMATION COLUMN
Problem
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 .
The expression string contains only non-negative integers, +, -, *, / operators , open ( and closing parentheses ) and empty spaces . The integer division should truncate toward zero.
You may assume that the given expression is always valid. All intermediate results will be in the range of [-2147483648, 2147483647].
Some examples:
"1 + 1" = 2 " 6-4 / 2 " = 4 "2*(5+5*2)/3+(6/2+8)" = 21 "(2+6* 3+5- (3*14/7+2)*5)+3"=-12
Note: Do not use the eval built-in library function.
Solutionclass Solution {
public int calculate(String s) {
s = s.replaceAll(" ", "");
if (s.length() == 0) return 0;
Stack stack = new Stack<>();
char sign = "+";
int res = 0, pre = 0, i = 0;
while (i < s.length()) {
char ch = s.charAt(i);
//consecutive digits as a number, save in `pre`
if (Character.isDigit(ch)) {
pre = pre*10+(ch-"0");
}
//recursively calculate results in parentheses
if (ch == "(") {
int j = findClosing(s.substring(i));
pre = calculate(s.substring(i+1, i+j));
i += j;
}
//for new signs, calculate with existing number/sign, then update number/sign
if (i == s.length()-1 || !Character.isDigit(ch)) {
switch (sign) {
case "+":
stack.push(pre); break;
case "-":
stack.push(-pre); break;
case "*":
stack.push(stack.pop()*pre); break;
case "/":
stack.push(stack.pop()/pre); break;
}
pre = 0;
sign = ch;
}
i++;
}
while (!stack.isEmpty()) res += stack.pop();
return res;
}
//Eliminate all "()" pairs, calculate the result in between and save in `pre`
private int findClosing(String s) {
int level = 0, i = 0;
for (i = 0; i < s.length(); i++) {
if (s.charAt(i) == "(") level++;
else if (s.charAt(i) == ")") {
level--;
if (level == 0) break;
} else continue;
}
return i;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/77149.html
摘要：復(fù)雜度思路用兩個(gè)來分別記錄當(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...
摘要：復(fù)雜度思路將字符串先轉(zhuǎn)換成后綴表達(dá)式，再將其出來。 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...
Problem 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 e...
摘要：題目鏈接，就是感覺條件有點(diǎn)多簡(jiǎn)單點(diǎn)的寫法，把直接用存在里面，就存成，存成題目鏈接這題就是碰到在加減后面怎么處理的問題。用一個(gè)來表示之前的，所以碰到現(xiàn)在是乘的時(shí)候就，除類似。 224. Basic Calculator 題目鏈接：https://leetcode.com/problems... stack，就是感覺條件有點(diǎn)多 public class Solution { pub...
閱讀 2531·2021-09-24 10:29
閱讀 3814·2021-09-22 15:46
閱讀 2582·2021-09-04 16:41
閱讀 2987·2019-08-30 15:53
閱讀 1268·2019-08-30 14:24
閱讀 3062·2019-08-30 13:19
閱讀 2177·2019-08-29 14:17
閱讀 3527·2019-08-29 12:55
