[LeetCode] 772. Basic Calculator III

BlackHole1 發布于2019-08-19 11:11 / 1944人閱讀

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.

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;
    }
}

云服務器 GPU云服務器 Calculator III LeetCode ucos-iii 消息隊列

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/77149.html

Leetcode[227] Basic Calculator II

摘要：復雜度思路用兩個來分別記錄當前的結果和操作符注意每一次統計當前的的時候，要看一下下一位的操作符。有一種的方法，是表示的是匹配任意的空白符，包括空格，制表符，換行符，中文全角空格等。也可以用更簡單的方法，。 LeetCode[227] Basic Calculator II Implement a basic calculator to evaluate a simple expres...

chaos_G 2019-08-14 16:55 評論0 收藏0
Leetcode[224] Basic Calculator

摘要：復雜度思路將字符串先轉換成后綴表達式，再將其出來。 Leetcode[224] Basic Calculator Implement a basic calculator to evaluate a simple expression string. The expression string may contain open ( and closing parentheses ),...

William_Sang 2019-08-14 16:55 評論0 收藏0
[LeetCode] 227. Basic Calculator II

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...

silvertheo 2019-08-19 11:11 評論0 收藏0
[LeetCode] 224. Basic Calculator

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...

xiangzhihong 2019-08-19 11:11 評論0 收藏0
224. Basic Calculator & 227. Basic Calculator

摘要：題目鏈接，就是感覺條件有點多簡單點的寫法，把直接用存在里面，就存成，存成題目鏈接這題就是碰到在加減后面怎么處理的問題。用一個來表示之前的，所以碰到現在是乘的時候就，除類似。 224. Basic Calculator 題目鏈接：https://leetcode.com/problems... stack，就是感覺條件有點多 public class Solution { pub...

_DangJin 2019-08-14 17:35 評論0 收藏0