Leetcode[224] Basic Calculator

William_Sang 發布于2019-08-14 16:55 / 1157人閱讀

摘要：復雜度思路將字符串先轉換成后綴表達式，再將其出來。

Leetcode[224] Basic Calculator

Implement a basic calculator to evaluate a simple expression string.
The expression string may contain open ( and closing parentheses ),
the plus +, minus sign - or * or /, non-negative integers and empty spaces .
You may assume that the given expression is always valid.
Some examples:
"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23
"1 + (2 - 3 * 4)" = -9;

Stack

復雜度
O(N), O(N)

思路
將字符串先轉換成后綴表達式，再將其evaluate出來。
前后綴表達式的轉換：
http://scriptasylum.com/tutor...
后綴表達式的evaluation:
http://scriptasylum.com/tutor...

代碼

public int basicCalculator(String s) {
    s = s.trim().replaceAll(" +", "");
    Stack stack = new Stack<>();
    StringBuilder builder = new StringBuilder();
    char[] arr = s.toCharArray();
    for(int i = 0; i < arr.length; i ++) {
        if(arr[i] == "(") {
            stack.push("(");
        }
        else if(arr[i] == ")") {
            while(!stack.isEmpty() && stack.peek() != "(") {
                builder.append(stack.pop());
            }
            // pop out the "("
            stack.pop();
        }
        else if(Character.isDigit(arr[i])) {
            int val = 0;
            for(int j = i; j < arr.length && Character.isDigit(arr[j]); j ++) {
                val *= 10;
                val += arr[j] - "0";
            }
            builder.append(val);
            i = j - 1;
        }
        else {
            while(!stack.isEmpty() && rank(stack.peek()) >= rank(arr[j])) {
                builder.append(stack.pop());
            }
            stack.push(arr[j]);
        }
    }
    while(!stack.isEmpty()) {
        builder.append(stack.pop());
    }
    return evaluate(builder.toString());
}

public int rank(Character ch) {
    if(ch == "+" || ch == "-") return 1;
    else if(ch == "*" || ch == "/") return 2;
    // "("
    return 0;
}

public int evaluate(String s) {
    char[] arr = s.toCharArray();
    Stack stack = new Stack<>();
    for(int i = 0; i < arr.length; i ++) {
        if(Character.isDigit(arr[i])) {
            stack.push(arr[i] - "0");
        }
        else {
            int op2 = stack.pop();
            int op1 = stack.pop();
            if(arr[i] == "+") {
                stack.push(op1 + op2);
            }
            else if(arr[i] == "-") {
                stack.push(op1 - op2);
            }
            else if(arr[i] == "*") {
                stack.push(op1 * op2);
            }
            else {
                stack.push(op1 / op2);
            }
        }
    }
    return stack.pop();
}

GPU云服務器云服務器 Calculator apache224 CS224n LeetCode

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

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

[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
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] 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] 772. Basic Calculator III

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

BlackHole1 2019-08-19 11:11 評論0 收藏0