1、括號匹配問題
. - 力扣（LeetCode）
1.1 思路分析
根據棧的先進后出原則，我們可以這樣解決問題：
遍歷字符串，遇見左括號就將左括號push入棧；遇見右括號就pop出棧，將出棧的元素和該右括號比較是否匹配，若匹配則繼續遍歷并比較，若不匹配則直接返回false。細分為以下幾種情況：
1.匹配（左右括號數量相同且匹配）：字符串遍歷完，且棧為空（右括號與左括號數量相等，且均匹配），則說明括號匹配，返回true。
2.不匹配（括號不匹配）：遍歷到的右括號和出棧的左括號比較是否匹配，一旦不匹配，立即返回false。
3.不匹配（左括號數量多）：當字符串遍歷完后，發現棧還不為空，則說明左括號多，不匹配。
4.不匹配（右括號多）：遍歷遇見右括號需將棧頂的左括號出棧，若要出棧時棧為空，則說明右括號多，不匹配。
1.2 代碼
public boolean isValid(String s) {//利用棧先進后出特點 解決問題Stack<Character> stack = new Stack<>();//遍歷字符串for(int i = 0; i < s.length(); i++) {char ch = s.charAt(i);//若為左括號 將括號入棧if(ch == '(' || ch == '{' || ch == '[') {stack.push(ch);}else {//遍歷到的為右括號 進入else//若棧為空 則說明右括號多 立即返回falseif(stack.isEmpty()) {return false;}//若棧不為空 則pop出棧 比較是否匹配 char ch2 = stack.pop();switch(ch) {//使用switch語句比較是否匹配 一旦不匹配 立即返回falsecase ')':if(ch2 != '(') {return false;}break;case ']':if(ch2 != '[') {return false;}break;case '}':if(ch2 != '{') {return false;}break;}}}//遍歷完成且棧為空 則說明匹配 if(!stack.isEmpty()) {return false;}return true;}2、棧的彈出、壓入序列
2.1 思路分析
以i遍歷pushV,每次都將將i下標的元素入棧，再將棧頂元素和j下標元素比較，
若相等：則出棧，j++，i++
不相等：則i++，j保持原位
注意：j++后，j下標與棧頂元素可能依然相等，此時要連續出棧。即j變化后，要繼續和棧頂元素比較。
- i遍歷完成，且j也遍歷也完成（此時棧肯定為空），說明出棧序列匹配
- 若i遍歷完成后，j還沒有遍歷完成（棧不為空），則說明出棧序列不匹配
因為只有棧頂元素和j下標元素相等時，才會出棧，j++
?2.2 代碼
public boolean IsPopOrder (int[] pushV, int[] popV) {Stack<Integer> stack = new Stack<>();int j = 0;for (int i = 0; i < pushV.length; i++) {//每次循環都會將pushV中i下標的元素入棧stack.push(pushV[i]);//因為j++后，元素可能連續出棧，所以要while循環//出棧后，棧可能出現空的情況，!stack.isEmpty()，防止出現空指針異常while (!stack.isEmpty() && stack.peek() == popV[j]) {j++;//若j下標和棧頂元素相同，則出棧stack.pop();}}//i遍歷完成，若此時j也遍歷完成（j == popV.length）,則說明出棧序列匹配return j == popV.length;}3、逆波蘭表達式（后綴表達式）求值
. - 力扣（LeetCode）
3.1 什么是逆波蘭表達式?
逆波蘭表達式，也稱為后綴表達式，是一種表達式的表示方法，其中運算符位于操作數之后。
后綴表達式由中綴表達式轉化而來，可以實現表達式的求值和計算，提高了計算機內存訪問的效率。而中綴表達式就是我們平時做運算的表達式。
那么如何將中綴表達式轉換為后綴表達式？
- 從左向右，以先乘除后加減的次序加括號
- 將括號中的相鄰兩項的運算符拿到括號的后面
- 去掉所有括號
?3.2 后綴表達式如何求值（思路分析）
我們拿到后綴表達式后，
- 遍歷表達式，若是非操作符元素（數字元素），則入棧
- 若遇到操作符元素，則出棧兩次，將第一次出棧的元素val2作為該操作符的右操作數，將第二次出棧的元素val1作為該操作符的左操作數，接著將所得結果入棧。
- 繼續遍歷，并重復以上操作
- 遍歷完成后，棧中只剩一個元素，該元素就是后綴表達式的值。
?3.3 代碼
class Solution {public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack<>();for (int i = 0; i < tokens.length; i++) {String str = tokens[i];if (!isOperator(str)) {//如果不是是操作符//則元素入棧int val = Integer.parseInt(str);//將字符串轉化為整型stack.push(val);} else {//如果是操作符//則彈出棧頂兩個元素//計算結果，并將結果入棧int val2 = stack.pop();int val1 = stack.pop();if (str.equals("+")) {stack.push(val1 + val2);}if (str.equals("-")) {stack.push(val1 - val2);}if (str.equals("*")) {stack.push(val1 * val2);}if (str.equals("/")) {stack.push(val1 / val2);}}}//遍歷完成后，棧中還有一個元素//該元素就是后綴表達式的值return stack.pop();}//判斷該元素是否為操作符private boolean isOperator(String str) {if (str.equals("+") || str.equals("-")|| str.equals("*") || str.equals("/")) {return true;}return false;}
}
