Java LeetCode篇-深入了解關(guān)于棧的經(jīng)典解法（棧實(shí)現(xiàn)：中綴表達(dá)式轉(zhuǎn)后綴）

這篇具有很好參考價(jià)值的文章主要介紹了Java LeetCode篇-深入了解關(guān)于棧的經(jīng)典解法（棧實(shí)現(xiàn)：中綴表達(dá)式轉(zhuǎn)后綴）。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

??博客主頁：?【小扳_-CSDN博客】
?感謝大家點(diǎn)贊??收藏?評論????

Java LeetCode篇-深入了解關(guān)于棧的經(jīng)典解法（棧實(shí)現(xiàn)：中綴表達(dá)式轉(zhuǎn)后綴）,Java LeetCode篇,java,算法,leetcode,鏈表

文章目錄

? ? ? ? 1.0 中綴表達(dá)式轉(zhuǎn)后綴說明

? ? ? ? 1.1 實(shí)現(xiàn)中綴表達(dá)式轉(zhuǎn)后綴思路

? ? ? ? 2.0 逆波蘭表達(dá)式求值

? ? ? ? 2.1 實(shí)現(xiàn)逆波蘭表達(dá)式求值思路

? ? ? ? 3.0 有效的括號

? ? ? ? 3.1 實(shí)現(xiàn)有效的括號思路

? ? ? ? 4.0 棧的壓入、彈出序列

? ? ? ? 4.1 實(shí)現(xiàn)棧的壓入、彈出序列思路

? ? ? ? 5.0 最小棧

? ? ? ? 5.1 實(shí)現(xiàn)最小棧思路

? ? ? ? 1.0 中綴表達(dá)式轉(zhuǎn)后綴說明

????????中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式是一種常見的算術(shù)表達(dá)式轉(zhuǎn)換方法，它將中綴表達(dá)式（即常見的人類習(xí)慣的表達(dá)方式，例如（"3 + 4 * 2"）轉(zhuǎn)換為后綴表達(dá)式（也稱為逆波蘭表達(dá)式，例如?" 3 4 2 * +"）。中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式的轉(zhuǎn)換過程通常使用棧來實(shí)現(xiàn)。

? ? ? ? 1.1 實(shí)現(xiàn)中綴表達(dá)式轉(zhuǎn)后綴思路

? ? ? ? 1.1.1 思路具體為：首先先來討論優(yōu)先級問題，分兩種情況。

? ? ? ? 情況一：不帶括號，對于?" + " " - "?" * " " / "，這個(gè)四種運(yùn)算符來定義優(yōu)先級大小，"+" "-" 優(yōu)先級大小可以設(shè)置為 1，" * " " / " 優(yōu)先級大小可以設(shè)置為 2 。

? ? ? ? 情況二：帶括號，對于 " ( "? 來說，將其優(yōu)先級設(shè)置為 0 ，為最小的優(yōu)先級。

? ? ? ? 再來討論代碼實(shí)現(xiàn)的流程：對于運(yùn)算符或者括號來說，將其放到棧中暫時(shí)存儲；對于數(shù)字 0 ~ 9 來說，將其拼接到可變字符串中。

? ? ? ? 1.1.2 接下來循環(huán)遍歷字符串：

? ? ? ? (1) 遇到非運(yùn)算符，直接拼串

? ? ? ? (2) 遇到 + - * /

? ? ? ? ? ? ? ? - 它的優(yōu)先級比棧頂運(yùn)算符高，入棧，如：棧中是 + ，當(dāng)前是 *?

? ? ? ? ? ? ? ? - 否則把棧里面的優(yōu)先級 >= 它的都出棧，它再進(jìn)棧，如棧中是 +* ，當(dāng)前是 -

? ? ? ? (3) 遍歷完成，棧里面剩余運(yùn)算符依次出棧拼接到字符串中

????????(4) 帶()

? ? ? ? ? ? ? ? - 遇到左括號直接入棧，左括號優(yōu)先級設(shè)置為 0 。

? ? ? ? ? ? ? ? - 遇到右括號就把棧里面到左括號為止的所有運(yùn)算符都出棧

代碼如下：

import java.util.Stack;

public class TurnToSuffix {
    public static void main(String[] args) {
        String s = "(a+b)*c";
        System.out.println(turnSuffix(s));

        String s1 = "(a+b*c-d)*e";
        System.out.println(turnSuffix(s1));

        String s2 = "a*(b+c)";
        System.out.println(turnSuffix(s2));
    }

    public static String turnSuffix(String s) {
        if (s.length() == 0) {
            return null;
        }

        StringBuilder str = new StringBuilder();
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);

            switch (ch) {
                case '(' -> {
                    //如果是有括號，直接進(jìn)棧
                    stack.push(ch);
                }
                case '+', '-','*','/' -> {
                    //比較優(yōu)先級，進(jìn)棧的優(yōu)先級高，不需要彈出；進(jìn)棧的優(yōu)先級底或者同一級別，需要彈出。
                    while ( !stack.isEmpty() && priority(ch) <= priority(stack.peek())) {
                        str.append(stack.pop());
                    }
                    stack.push(ch);

                }
                case ')' -> {
                    while ( !stack.isEmpty() && stack.peek() != '(') {
                        str.append(stack.pop());
                    }
                    stack.pop();
                }
                default -> {
                    str.append(ch);
                }
            }

        }
        int num = stack.size();
        for (int j = 0; j < num; j++) {
            str.append(stack.pop());
        }
        return str.toString();
    }

    public static int priority(char f) {
        if (f == '(') {
            return 0;
        } else if (f == '+' || f == '-') {
            return 1;
        }else if (f == '*' || f == '/' ) {
            return 2;
        }
        return -1;
    }
}

? ? ? ? 2.0 逆波蘭表達(dá)式求值

?????????逆波蘭表達(dá)式（也稱為后綴表達(dá)式）是一種不需要括號來表示運(yùn)算順序的算術(shù)表達(dá)式。它的計(jì)算方式是從左到右掃描表達(dá)式，遇到操作數(shù)就將其壓入棧中，遇到操作符就從棧中彈出相應(yīng)數(shù)量的操作數(shù)進(jìn)行運(yùn)算，并將結(jié)果再次壓入棧中。最終棧中的唯一元素就是表達(dá)式的值。

題目：

????????給你一個(gè)字符串?dāng)?shù)組?tokens?，表示一個(gè)根據(jù)?逆波蘭表示法?表示的算術(shù)表達(dá)式。

請你計(jì)算該表達(dá)式。返回一個(gè)表示表達(dá)式值的整數(shù)。

注意：

有效的算符為?'+'、'-'、'*'?和?'/'?。

每個(gè)操作數(shù)（運(yùn)算對象）都可以是一個(gè)整數(shù)或者另一個(gè)表達(dá)式。

兩個(gè)整數(shù)之間的除法總是?向零截?cái)?。

表達(dá)式中不含除零運(yùn)算。

輸入是一個(gè)根據(jù)逆波蘭表示法表示的算術(shù)表達(dá)式。

答案及所有中間計(jì)算結(jié)果可以用?32 位?整數(shù)表示。

示例?1：
輸入：tokens = ["2","1","+","3","*"]
輸出：9
解釋：該算式轉(zhuǎn)化為常見的中綴算術(shù)表達(dá)式為：((2 + 1) * 3) = 9

? ? ? ? 2.1 實(shí)現(xiàn)逆波蘭表達(dá)式求值思路

? ? ? ? 思路具體為：遍歷字符串?dāng)?shù)組，將遍歷遇到的非運(yùn)算符都要存放在棧中；遇到運(yùn)算符需要將棧中的數(shù)據(jù)彈出棧，第一個(gè)彈出的數(shù)據(jù)稱為右操作數(shù)，第二個(gè)彈出來的數(shù)據(jù)稱為左操作數(shù)。接著對應(yīng)相應(yīng)的運(yùn)算符進(jìn)行對該這兩個(gè)數(shù)據(jù)操作，得到的計(jì)算結(jié)果需要重新壓入棧中。最后循環(huán)結(jié)束，棧中存放的就是該表達(dá)式最終的結(jié)果了。

代碼如下：

class Solution {
    public static int evalRPN(String[] tokens) {
        LinkedList<Integer> stack = new LinkedList<>();
        for (int i = 0; i < tokens.length; i++) {
            int a = 0;
            int b = 0;
            switch (tokens[i]) {
                case "+":
                    b = stack.pop();
                    a = stack.pop();
                    stack.push(a + b);
                    break;
                case "-":
                    b = stack.pop();
                    a = stack.pop();
                    stack.push(a - b);
                    break;
                case "*":
                    b = stack.pop();
                    a = stack.pop();
                    stack.push(a * b);
                    break;
                case "/":
                    b = stack.pop();
                    a = stack.pop();
                    stack.push(a / b);
                    break;
                default:
                    stack.push(Integer.parseInt(tokens[i]));
                    break;
            }
        }
        return stack.pop();
    }
}

? ? ? ? 需要注意的點(diǎn)是：從字符串?dāng)?shù)組中得到的非運(yùn)算符是，需要將其轉(zhuǎn)換為 int 的包裝類型。

? ? ? ? 3.0 有效的括號

題目：

????????給定一個(gè)只包括?'('，')'，'{'，'}'，'['，']'?的字符串?s?，判斷字符串是否有效。

有效字符串需滿足：

左括號必須用相同類型的右括號閉合。

左括號必須以正確的順序閉合。

每個(gè)右括號都有一個(gè)對應(yīng)的相同類型的左括號。

示例 1：
輸入：s = "()"
輸出：true
示例?2：
輸入：s = "()[]{}"
輸出：true
該題的 LeetCode 鏈接：20.?有效的括號

? ? ? ? 3.1 實(shí)現(xiàn)有效的括號思路

? ? ? ? 具體思路為：遍歷字符串，每一次循環(huán)得到的字符可以大致分為兩種情況：

? ? ? ? 第一種情況：遇到的是右括號，無論是 ' ( '? ' { '? ' [ '? 的其中一種，都需要將其相反的符號壓入棧中。如：遇到的是 ' ( ' ，那么需要壓入棧的是 ' ) ' 。

? ? ? ? 第二種情況：遇到的是左括號，無論是? ' ) '? ' } '? ' ] '??的其中一種，先要判斷棧中是否為空，如果為空，直接返回 false ；當(dāng)不為空時(shí)，若判斷棧頂?shù)睦ㄌ柺欠窀龅降淖罄ㄌ栂嗟龋绻嗟?，將棧頂?shù)睦ㄌ枏棾?，若不相等，直接返?false 。

? ? ? ? 最后循環(huán)結(jié)束了，判斷棧是否為空，如果棧為空了，那么說明都一一對稱，有相應(yīng)的括號與之匹配；如果不為空，那么說明，不是全部的括號都要相應(yīng)的括號對應(yīng)。

代碼如下：

class Solution {
public  static boolean isValid(String s) {
        if (s.length() == 0) {
            return false;
        }
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {

            char ch = s.charAt(i);
            switch (ch) {
                case '[' -> {
                    stack.push(']');
                }
                case '{' -> {
                    stack.push('}');
                }
                case '(' -> {
                    stack.push(')');
                }
                default -> {
                    if (stack.empty()) {
                        return false;
                    }
                    if (ch != stack.peek()) {
                        return false;
                    } else if (ch == stack.peek()) {
                        stack.pop();
                    }

                }
            }

        }
        return stack.empty();
    }
}

? ? ? ? 4.0 棧的壓入、彈出序列

題目：

????????輸入兩個(gè)整數(shù)序列，第一個(gè)序列表示棧的壓入順序，請判斷第二個(gè)序列是否可能為該棧的彈出順序。假設(shè)壓入棧的所有數(shù)字均不相等。例如序列1,2,3,4,5是某棧的壓入順序，序列4,5,3,2,1是該壓棧序列對應(yīng)的一個(gè)彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列。

1. 0<=pushV.length ==?popV.length <=1000

2. -1000<=pushV[i]<=1000

3.?pushV?的所有數(shù)字均不相同

示例1

輸入：
[1,2,3,4,5],[4,5,3,2,1]
返回值：
true
說明：
可以通過push(1)=>push(2)=>push(3)=>push(4)=>pop()=>push(5)=>pop()=>pop()=>pop()=>pop()
這樣的順序得到[4,5,3,2,1]這個(gè)序列，返回true      
該題的鏈接為：棧的壓入、彈出序列_?？皖}霸_?？途W(wǎng) (nowcoder.com)? ? ? ?

? ? ? ? 4.1 實(shí)現(xiàn)棧的壓入、彈出序列思路

? ? ? ? 第一個(gè)序列表示棧的壓入順序、第二個(gè)序列可能為該棧的彈出順序

? ? ? ? 具體思路為：遍歷第一個(gè)序列，每一次得到的數(shù)值都要跟第二個(gè)序列索引從 0 開始到該序列長度 - 1 比較，如果從第一個(gè)序列得到的數(shù)值跟第二個(gè)序列的數(shù)值不相同時(shí)，需要將第一序列的數(shù)值壓入棧中；如果從第二個(gè)序列得到的數(shù)值跟第二個(gè)序列的數(shù)值相同時(shí)，需要將第一個(gè)序列的數(shù)值彈出棧中，接著第二個(gè)序列跳到下一個(gè)數(shù)值跟棧中的數(shù)值進(jìn)行比較，若相同，棧中繼續(xù)彈出，第二個(gè)序列繼續(xù)跳到下一個(gè)。若不相同，繼續(xù)遍歷第一個(gè)序列。

? ? ? ? 可以簡單的理解為：每一次循環(huán)第一個(gè)序列得到數(shù)據(jù)都要放到棧中，接著跟第二個(gè)序列的數(shù)據(jù)進(jìn)行比較。如果棧頂?shù)臄?shù)據(jù)跟第二個(gè)序列的數(shù)值相同時(shí)，需要將其棧頂元素彈出，還需要將第二個(gè)序列移到下一個(gè)元素。接著繼續(xù)比較，直到棧頂元素跟第二個(gè)序列的元素不相等是，繼續(xù)遍歷第一個(gè)序列，直到第一個(gè)序列遍歷完畢。最后判斷占是否為空，若為空，返回 true ；若不為空，返回 false 。

代碼如下：

import java.util.*;


public class Solution {
    /**
     * 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請勿修改，直接返回方法規(guī)定的值即可
     *
     * 
     * @param pushV int整型一維數(shù)組 
     * @param popV int整型一維數(shù)組 
     * @return bool布爾型
     */
    public boolean IsPopOrder (int[] pushV, int[] popV) {
        // write code here
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for(int i = 0; i < pushV.length ; i++) {

            stack.push(pushV[i]);

            while( !stack.isEmpty() && j < popV.length && stack.peek() == popV[j]) {
                stack.pop();
                j++;
            }

        }
        return stack.isEmpty();

    }
}

? ? ? ? 需要注意的是，在內(nèi)層循環(huán)時(shí)，要保證棧中不為空且不能超過第二個(gè)序列的長度。

? ? ??

? ? ? ? 5.0 最小棧

題目：

????????設(shè)計(jì)一個(gè)支持?push?，pop?，top?操作，并能在常數(shù)時(shí)間內(nèi)檢索到最小元素的棧。

實(shí)現(xiàn)?MinStack?類:

MinStack()?初始化堆棧對象。

void push(int val)?將元素val推入堆棧。

void pop()?刪除堆棧頂部的元素。

int top()?獲取堆棧頂部的元素。

int getMin()?獲取堆棧中的最小元素。

示例 1:
輸入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

輸出：
[null,null,null,null,-3,null,0,-2]

解釋：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.
該題的 LeetCode 鏈接為：155.?最小棧

? ? ? ? 5.1 實(shí)現(xiàn)最小棧思路

? ? ? ? 具體思路為：因?yàn)樾枰涗洍Ｖ械淖钚≡?，所以需要用?span style="color:#fe2c24;">兩個(gè)棧，對于 stack 棧來說，就正常的壓棧、出棧、查看棧頂元素等操作即可；

? ? ? ? 壓棧處理：對于 minStack 棧來說，當(dāng)該棧為空時(shí)，stack 壓棧時(shí)，minStack 也要壓棧相同的元素；當(dāng) minStack 不為空時(shí)，satck 壓棧時(shí)，minStack 需要先判斷該棧頂元素的值是否大于需要壓入棧的元素的值，若大于等于，則 minStzck 需要將其壓入棧，若小于，則不需要進(jìn)行任何操作。

? ? ? ? 出棧處理：需要先判斷 stack 是否為空棧，如果是空棧，則不需要進(jìn)行出棧處理。如果不為空棧，stack 需要出棧，但是對于 nimStack 不一定需要出棧，若 stack 的棧頂與 nimStack 的棧頂元素相同時(shí)，nimStack 需要出棧。若不相同，則不需要出棧。

? ? ? ? 查看棧頂元素處理：直接返回 stack.pop() 即可。

? ? ? ? 查看最小棧的元素：直接返回 minStack.peek() 即可。

代碼如下：

class MinStack {

    Stack<Integer> stack;
    Stack<Integer> minStack ;
    public MinStack() {
        stack  = new Stack<>();
        minStack = new Stack<>();

    }
    
    public void push(int val) {
        stack.push(val);
        if(minStack.isEmpty()) {
            minStack.push(val);
        }else if(minStack.peek() >= val) {
            minStack.push(val);
        }

    }
    
    public void pop() {
        if(stack.pop().equals(minStack.peek())){
            minStack.pop();
        }
        
    }
    
    public int top() {
        return stack.peek();

    }
    
    public int getMin() {
        return minStack.peek();

    }
}

? ? ? ? 需要注意的是， stack 與 minStack 的棧頂元素進(jìn)行比較時(shí)，需要用 equals() 方法進(jìn)行比較，不然會發(fā)生問題。

Java LeetCode篇-深入了解關(guān)于棧的經(jīng)典解法（棧實(shí)現(xiàn)：中綴表達(dá)式轉(zhuǎn)后綴）,Java LeetCode篇,java,算法,leetcode,鏈表文章來源地址http://www.zghlxwxcb.cn/news/detail-757901.html

到了這里，關(guān)于Java LeetCode篇-深入了解關(guān)于棧的經(jīng)典解法（棧實(shí)現(xiàn)：中綴表達(dá)式轉(zhuǎn)后綴）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！