[LeetCode] 772. Basic Calculator III
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.
Solution
class 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;
}
}
์ด ๋ด์ฉ์ ํฅ๋ฏธ๊ฐ ์์ต๋๊น?
ํ์ฌ ๊ธฐ์ฌ๊ฐ ์ฌ๋ฌ๋ถ์ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ์ง ๋ชปํ๋ ๊ฒฝ์ฐ AI ์์ง์ ๋จธ์ ๋ฌ๋ ๋ถ์(์ค๋งํธ ๋ชจ๋ธ์ด ๋ฐฉ๊ธ ๋ง๋ค์ด์ ธ ๋ถ์ ํํ ๊ฒฝ์ฐ๊ฐ ์์ ์ ์์)์ ํตํด ๊ฐ์ฅ ์ ์ฌํ ๊ธฐ์ฌ๋ฅผ ์ถ์ฒํฉ๋๋ค:
Is Eclipse IDE dying?In 2014 the Eclipse IDE is the leading development environment for Java with a market share of approximately 65%. but ac...
ํ ์คํธ๋ฅผ ์์ ๋กญ๊ฒ ๊ณต์ ํ๊ฑฐ๋ ๋ณต์ฌํ ์ ์์ต๋๋ค.ํ์ง๋ง ์ด ๋ฌธ์์ URL์ ์ฐธ์กฐ URL๋ก ๋จ๊ฒจ ๋์ญ์์ค.
CC BY-SA 2.5, CC BY-SA 3.0 ๋ฐ CC BY-SA 4.0์ ๋ฐ๋ผ ๋ผ์ด์ผ์ค๊ฐ ๋ถ์ฌ๋ฉ๋๋ค.
์ข์ ์นํ์ด์ง ์ฆ๊ฒจ์ฐพ๊ธฐ
๊ฐ๋ฐ์ ์ฐ์ ์ฌ์ดํธ ์์ง
๊ฐ๋ฐ์๊ฐ ์์์ผ ํ ํ์ ์ฌ์ดํธ 100์ ์ถ์ฒ ์ฐ๋ฆฌ๋ ๋น์ ์ ์ํด 100๊ฐ์ ์์ฃผ ์ฌ์ฉํ๋ ๊ฐ๋ฐ์ ํ์ต ์ฌ์ดํธ๋ฅผ ์ ๋ฆฌํ์ต๋๋ค