前言
提示：快樂的人沒有過去，不快樂的人除了過去一無所有。 --理查德·弗蘭納根《深入北方的小路》
棧的進(jìn)階來了，還記得棧的使用場(chǎng)景嗎？表達(dá)式和符號(hào)，這不就來了
1. 計(jì)算器問題
參考題目介紹：227. 基本計(jì)算器 II - 力扣（LeetCode）
計(jì)算問題在棧的運(yùn)用也是非常廣泛的。在乘除優(yōu)先于加減計(jì)算，我們需要考慮所有的乘除運(yùn)算，并將這些乘除運(yùn)算后的整數(shù)放回原來對(duì)應(yīng)的表達(dá)式中，隨后整個(gè)表達(dá)式的值等于一系列整數(shù)加減后的運(yùn)算值。
基于這樣的想法，我們可以使用的們的老朋友棧了，保存這些（進(jìn)行乘除運(yùn)算后的）整數(shù)值。對(duì)于加減后的數(shù)字，將其直接壓入棧中，對(duì)于乘除后的數(shù)字，我可以直接與棧頂元素計(jì)算，并替換棧頂元素作為計(jì)算后的結(jié)果。
具體來說，我們遍歷字符串s，并用變量preSign來記錄每個(gè)數(shù)字之前的運(yùn)算符，對(duì)于第一個(gè)數(shù)字，其之前的運(yùn)算符視為加號(hào)。每次遍歷到數(shù)組的末尾時(shí)，根據(jù)preSign來決定計(jì)算方式
- 加號(hào)：將數(shù)字壓入棧中
- 減號(hào)：將數(shù)字的相反數(shù)壓入棧中
- 乘除號(hào)：計(jì)算數(shù)字與棧頂元素，并將棧頂元素替換為計(jì)算結(jié)果。
代碼實(shí)現(xiàn)中，讀到一個(gè)運(yùn)算符，或者遍歷到字符串末尾,，就認(rèn)為遍歷到了數(shù)字末尾。處理完該數(shù)字后，更新preSign為當(dāng)前遍歷的字符。遍歷完字符串s后，將棧中的元素累加，即為該表達(dá)式的結(jié)果。
/**
* 實(shí)現(xiàn)計(jì)算器問題
* @param s
* @return
*/
public static int calculate(String s) {
Deque<Integer> stack = new ArrayDeque<Integer>();
// 計(jì)算可以都看做時(shí) + 這里是前一個(gè)符號(hào)
Character preSign = '+';
int num = 0;
int n = s.length();
for (int i = 0; i < n; i++) {
if (Character.isDigit(s.charAt(i))) {
// 字符轉(zhuǎn)數(shù)字 考慮到大于10 的情況
num = num * 10 + s.charAt(i) - '0';
}
if (!Character.isDigit(s.charAt(i)) && s.charAt(i) != ' ' || i == n - 1) {
switch (preSign) {
case '+':
stack.push(num);
break;
case '-':
stack.push(-num);
break;
case '*': // 5 * 2
stack.push(stack.pop() * num);
break;
case '/': // 10 / 2
stack.push(stack.pop() / num);
break;
default:
break;
}
// 更新前一個(gè)符號(hào) 這樣就可以確定乘除優(yōu)先了
preSign = s.charAt(i);
num = 0;
}
}
int ans = 0;
while(!stack.isEmpty()){
ans += stack.pop();
}
return ans;
}
注意：
-
perSign 指的是前一個(gè)運(yùn)算符號(hào)（首次默認(rèn)看作是＋號(hào)）
-
慢一次計(jì)算 就可以確保乘除優(yōu)先了
2. 逆波蘭表達(dá)式問題
參考題目介紹：150. 逆波蘭表達(dá)式求值 - 力扣（LeetCode）
說實(shí)話這個(gè)題頗有難度，可以放在學(xué)習(xí)完二叉樹再來看??
表達(dá)式計(jì)算式編譯原理，自然語言處理，文本分析等領(lǐng)域非?？粗氐膯栴}，這里我們就挑這個(gè)題目練手，逆波蘭表達(dá)式。
這道題看似困難，實(shí)則真困難吶，你要是不知道什么是表達(dá)式，完了，你不會(huì)了。這里的表達(dá)式就好比一起上小學(xué)學(xué)的（2+1）* 3這樣字的，根據(jù)不同的記法，就有前綴，中綴，后綴之說，區(qū)別呢在于運(yùn)算符號(hào)相對(duì)于操作數(shù)的位置，前綴就是運(yùn)算符號(hào)在操作數(shù)前面，那后綴和中綴呢？你想想？
??聰明講個(gè)笑話：
有一天，一只螞蟻遇到了一只蝸牛。螞蟻問蝸牛：“為什么我們走路的時(shí)候總是把頭抬得那么高？”蝸牛回答：“因?yàn)槲覀兊哪繕?biāo)在地上。”
對(duì)應(yīng)的三種表達(dá)式：
中綴表達(dá)式：（ 1 + 2 ） * 3
前綴表達(dá)式： + 1 2 * 3
后綴表達(dá)式： 1 2 + 3 *
從上面看，中綴的表達(dá)式更像是我們常見的，它作為一種通用的算數(shù)運(yùn)算和邏輯公式表示，操作符以中綴形式處于操作數(shù)的中間。雖然我們的大腦很容易就可以理解這些分析最終拿到結(jié)果，但是對(duì)于計(jì)算機(jī)來說，就很頭疼了，計(jì)算機(jī)在做表達(dá)式計(jì)算的時(shí)候，通常是需要將中綴表達(dá)式轉(zhuǎn)換為前綴或者后綴表達(dá)式再進(jìn)行求值的。前綴表達(dá)式的運(yùn)算符位于兩個(gè)相應(yīng)操作數(shù)之前，前綴表達(dá)式又被稱為前綴記法或者波蘭是，而后綴表達(dá)式就是你波蘭式了。
觀察后我們就可以看出，根據(jù)特點(diǎn)將數(shù)字保存下來，遇到符號(hào)就計(jì)算。比如：1 2 + 3 * 遇到+ ，我們就好1 和 2 加起來，得到結(jié)果 3 然后在進(jìn)行計(jì)算 得到結(jié)果 9 .
這樣得話之不是容易一些，遇到數(shù)字就進(jìn)棧，遇到運(yùn)算符就取出棧中的最上面的兩個(gè)元素進(jìn)行計(jì)算，最后再將結(jié)果入棧。實(shí)現(xiàn)代碼會(huì)不會(huì)簡(jiǎn)單一些：文章來源：http://www.zghlxwxcb.cn/news/detail-689350.html
public class EvalRPN {
public static int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<Integer>();
for (String token : tokens) {
if (!Character.isDigit(token.charAt(0)) && token.length() == 1) {
// 取出棧頂?shù)臄?shù)字
int a = stack.pop();
int b = stack.pop();
// 做運(yùn)算
switch (token) {
case "+": // a b +
stack.push(a + b);
break;
case "-": // a b -
stack.push(a - b);
break;
case "*": // a b *
stack.push(a * b);
break;
case "/": // a b /
stack.push(a / b);
break;
default:
break;
}
}else {
// 直接存入棧中
stack.push(Integer.parseInt(token));
}
}
return stack.pop();
}
總結(jié)
提示：棧的運(yùn)用，表達(dá)式策略，逆波蘭。文章來源地址http://www.zghlxwxcb.cn/news/detail-689350.html
到了這里，關(guān)于算法通過村第四關(guān)-棧黃金筆記|表達(dá)式問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
