<ul id="wk0cu"></ul>

leetcode225 basic calculator

Cciradih 發布于2019-08-15 13:30 / 979人閱讀

摘要：題目中也給出了例子。因為沒有更高優先級的運算符，因此一旦我們遇到連續的形式，就可以立刻計算出結果。目前的想法是，一旦遇到括號，就將括號內的內容作為一個新的起點進行計算，但是括號前的內容也就是括號所位于的上下文需要通過棧來記錄。

題目要求

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 .

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
Note: Do not use the eval built-in library function.

實現一個簡單的計算器，這個計算器可以計算以String為輸入的中序表達式。這個中序表達式包含(),+,-和數字。題目中也給出了例子。
還有一個比較特殊的情況為(3)-(4)-(5) = -6

思路和代碼

其實這道題等價于如何計算中序表達式，且比四則運算還要簡單因為沒有*和/。我們除了可以選擇將其轉化為后序表達式然后再對后序表達式進行，還可以在一次遍歷的過程中就將其計算出來。
因為沒有更高優先級的運算符，因此一旦我們遇到連續的a+b形式，就可以立刻計算出結果。我們需要考慮的特殊情況是一旦遇到括號應該怎么辦。
目前的想法是，一旦遇到括號，就將括號內的內容作為一個新的起點進行計算，但是括號前的內容（也就是括號所位于的上下文）需要通過棧來記錄。那么這個上下文應該存儲什么內容呢？應該是括號前的符號以及括號前至上一個括號的計算結果。
這里講的有點復雜了，我們可以看一個例子來理解一下。

現在我們要計算3+4-7+(5-9-(4)+6)-1這個式子，我們使用result來記錄當前的結果，用sign來記錄當前計算結果的正負性，再用一個棧s來記錄上下文情況。那么遍歷過程如下：
1.3+4-6-(5-9-(4)+6)-1 result = 3 sign=1 s=[]
2.3+4-6-(5-9-(4)+6)-1 result = 3 sign=1 s=[]
3.3+4-6-(5-9-(4)+6)-1 result = 7 sign=1 s=[]
4.3+4-6-(5-9-(4)+6)-1 result = 7 sign=-1 s=[]
5.3+4-6-(5-9-(4)+6)-1 result = 1 sign=-1 s=[]
6.3+4-6-(5-9-(4)+6)-1 result = 1 sign=-1 s=[]
7.3+4-6-(5-9-(4)+6)-1 result = 1 sign=1 s=[1,-1] 這時棧中的內容分別帶包前面已經計算的值0和該位的正負形-1。同時因為即將開始一個新的計算，要將result初始化為0，sign初始化為1
8.3+4-6-(5-9-(4)+6)-1 result = 5 sign=1 s=[1,-1]
9.3+4-6-(5-9-(4)+6)-1 result = 5 sign=-1 s=[1,-1]
10.3+4-6-(5-9-(4)+6)-1 result = -4 sign=-1 s=[1,-1]
11.3+4-6-(5-9-(4)+6)-1 result = -4 sign=-1 s=[1,-1]
12.3+4-6-(5-9-(4)+6)-1 result = 0 sign=1 s=[1,-1,-4,-1]
13.3+4-6-(5-9-(4)+6)-1 result = 4 sign=1 s=[1,-1,-4,-1]
14.3+4-6-(5-9-(4)+6)-1 result = 4*(-1)-4=-8 sign=1 s=[1,-1] 遇到右括號，將棧中的上下文和當前的結果result進行計算得出括號中的最終結果
15.3+4-6-(5-9-(4)+6)-1 result = -8 sign=1 s=[1,-1]
16.3+4-6-(5-9-(4)+6)-1 result = -2*(-1) + 1=3 sign=1 s=[]
17.3+4-6-(5-9-(4)+6)-1 result = 3 sign=-1 s=[]
18.3+4-6-(5-9-(4)+6)-1 result = 2 sign=-1 s=[]

代碼如下：

    public  int calculate(String s) {
        int len = s.length(), sign = 1, result = 0;
        Stack stack = new Stack();
        for (int i = 0; i < len; i++) {
            if (Character.isDigit(s.charAt(i))) {
                int sum = s.charAt(i) - "0";
                while (i + 1 < len && Character.isDigit(s.charAt(i + 1))) {
                    sum = sum * 10 + s.charAt(i + 1) - "0";
                    i++;
                }
                result += sum * sign;
            } else if (s.charAt(i) == "+")
                sign = 1;
            else if (s.charAt(i) == "-")
                sign = -1;
            else if (s.charAt(i) == "(") {
                stack.push(result);
                stack.push(sign);
                result = 0;
                sign = 1;
            } else if (s.charAt(i) == ")") {
                result = result * stack.pop() + stack.pop();
            }

        }
        return result;
    }

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

GPU云服務器云服務器 Calculated Calculation Calculator Leetcod

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/68135.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] 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
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