資訊專欄INFORMATION COLUMN
摘要：題目中也給出了例子。因?yàn)闆](méi)有更高優(yōu)先級(jí)的運(yùn)算符，因此一旦我們遇到連續(xù)的形式，就可以立刻計(jì)算出結(jié)果。目前的想法是，一旦遇到括號(hào)，就將括號(hào)內(nèi)的內(nèi)容作為一個(gè)新的起點(diǎn)進(jìn)行計(jì)算，但是括號(hào)前的內(nèi)容也就是括號(hào)所位于的上下文需要通過(guò)棧來(lái)記錄。
題目要求
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.
實(shí)現(xiàn)一個(gè)簡(jiǎn)單的計(jì)算器，這個(gè)計(jì)算器可以計(jì)算以String為輸入的中序表達(dá)式。這個(gè)中序表達(dá)式包含(),+,-和數(shù)字。題目中也給出了例子。
還有一個(gè)比較特殊的情況為(3)-(4)-(5) = -6
其實(shí)這道題等價(jià)于如何計(jì)算中序表達(dá)式，且比四則運(yùn)算還要簡(jiǎn)單因?yàn)闆](méi)有*和/。我們除了可以選擇將其轉(zhuǎn)化為后序表達(dá)式然后再對(duì)后序表達(dá)式進(jìn)行，還可以在一次遍歷的過(guò)程中就將其計(jì)算出來(lái)。
因?yàn)闆](méi)有更高優(yōu)先級(jí)的運(yùn)算符，因此一旦我們遇到連續(xù)的a+b形式，就可以立刻計(jì)算出結(jié)果。我們需要考慮的特殊情況是一旦遇到括號(hào)應(yīng)該怎么辦。
目前的想法是，一旦遇到括號(hào)，就將括號(hào)內(nèi)的內(nèi)容作為一個(gè)新的起點(diǎn)進(jìn)行計(jì)算，但是括號(hào)前的內(nèi)容（也就是括號(hào)所位于的上下文）需要通過(guò)棧來(lái)記錄。那么這個(gè)上下文應(yīng)該存儲(chǔ)什么內(nèi)容呢？應(yīng)該是括號(hào)前的符號(hào)以及括號(hào)前至上一個(gè)括號(hào)的計(jì)算結(jié)果。
這里講的有點(diǎn)復(fù)雜了，我們可以看一個(gè)例子來(lái)理解一下。
現(xiàn)在我們要計(jì)算3+4-7+(5-9-(4)+6)-1這個(gè)式子，我們使用result來(lái)記錄當(dāng)前的結(jié)果，用sign來(lái)記錄當(dāng)前計(jì)算結(jié)果的正負(fù)性，再用一個(gè)棧s來(lái)記錄上下文情況。那么遍歷過(guò)程如下：
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] 這時(shí)棧中的內(nèi)容分別帶包前面已經(jīng)計(jì)算的值0和該位的正負(fù)形-1。同時(shí)因?yàn)榧磳㈤_(kāi)始一個(gè)新的計(jì)算，要將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] 遇到右括號(hào)，將棧中的上下文和當(dāng)前的結(jié)果result進(jìn)行計(jì)算得出括號(hào)中的最終結(jié)果
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;
}
想要了解更多開(kāi)發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/68135.html
摘要：復(fù)雜度思路用兩個(gè)來(lái)分別記錄當(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...
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...
摘要：復(fù)雜度思路將字符串先轉(zhuǎn)換成后綴表達(dá)式，再將其出來(lái)。 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...
閱讀 2611·2021-11-17 09:33
閱讀 3974·2021-10-19 11:46
閱讀 924·2021-10-14 09:42
閱讀 2270·2021-09-22 15:41
閱讀 4246·2021-09-22 15:20
閱讀 4660·2021-09-07 10:22
閱讀 2323·2021-09-04 16:40
閱讀 827·2019-08-30 15:52
