括號(hào)匹配校驗(yàn)

假設(shè)表達(dá)式中允許包含兩種括號(hào)，圓括號(hào)和方括號(hào)，其嵌套順序隨意，即[()[]]、[([][])]和[]()[]等為正確格式，[(])或([())等均為不正確格式。要求編寫一個(gè)程序檢驗(yàn)括號(hào)輸入是否正確。

思路整理

此題我們使用棧的后進(jìn)先出的原則來實(shí)現(xiàn)，思路如下：

1. 如果以]或)開頭那么括號(hào)肯定是不匹配的。
2. 將接收到的字符串拆分成單個(gè)字符
3. 遍歷入棧
   • 若當(dāng)前?？?，則直接入棧
   • 若當(dāng)前棧不為空，則取出棧頂數(shù)據(jù)與當(dāng)前數(shù)據(jù)做對(duì)比。若兩個(gè)括號(hào)匹配，則取出棧頂數(shù)據(jù)。否則將當(dāng)前數(shù)據(jù)入棧

4. 遍歷完成后檢查棧是否為空。若為空則說明校驗(yàn)成功，否則檢驗(yàn)失敗

   
   
   956be32c0c934679801e1600a530d56cpng

代碼實(shí)現(xiàn)

package com.codestd.study.stack;

import java.util.Stack;
/**
 * 括號(hào)校驗(yàn)
 * @author jaune
 * @since 1.0.0
 */
public class BracketChecker {

    /**
     * 校驗(yàn)括號(hào)是否正確
     * @param in 輸入括號(hào)字符串
     */
    public static boolean check(String in) {
        char[] chars = in.toCharArray();
        Stack<Character> stack = new Stack<>();
        for (char aChar : chars) {
            // 如果不是括號(hào)字符直接丟棄
            if (isBracket(aChar)) {
                if (stack.isEmpty()) {
                    stack.push(aChar);
                } else {
                    char stackChar = stack.peek();
                    // 注意這里的順序，一定是棧中的是前括號(hào)，比較的是后括號(hào)才行。順序不能亂。)( 這種格式是錯(cuò)誤的。
                    if (checkPairBracket(stackChar, aChar)) {
                        stack.pop();
                    } else {
                        stack.push(aChar);
                    }
                }
            }
        }

        return stack.isEmpty();
    }

    /**
     * 檢驗(yàn)前括號(hào)和后括號(hào)是否匹配
     * @param ch1 前括號(hào)
     * @param ch2 后括號(hào)
     */
    public static boolean checkPairBracket(char ch1, char ch2) {
        return ch1 == '(' && ch2 == ')' || ch1 == '[' && ch2 == ']';
    }

    /**
     * 檢查是否為括號(hào)字符
     */
    public static boolean isBracket(char ch) {
        return ch == '(' || ch == ')' || ch == '[' || ch == ']';
    }
}

此題中只說了小括號(hào)和中括號(hào)，如果再加上大括號(hào)，或者書名號(hào)等成對(duì)出現(xiàn)的字符，核心的代碼不用做修改，只需要修改checkPairBracket和isBracket即可。無論多少種括號(hào)，校驗(yàn)的原理都是一樣的。

測(cè)試代碼如下：

import static org.assertj.core.api.Assertions.*;

/**
 * Test for {@link BracketChecker}
 */
public class BracketCheckerTest {

    @Test
    public void test() {
        String s1 = "[]()[(())()]";
        assertThat(BracketChecker.check(s1)).isTrue();
        String s2 = ")[]()[]";
        assertThat(BracketChecker.check(s2)).isFalse();
        String s3 = "[(])[]";
        assertThat(BracketChecker.check(s3)).isFalse();
    }
}

以上測(cè)試代碼已測(cè)試通過。由于棧的底層實(shí)現(xiàn)是數(shù)組或鏈表，所以使用數(shù)組的方式也可以解決此問題。只需要一個(gè)指針指向數(shù)組尾部數(shù)據(jù)即可。

行編輯程序

一個(gè)簡(jiǎn)單的行編輯器程序的功能是：接收用戶從終端輸入的程序或數(shù)據(jù)，對(duì)用戶輸入的一行數(shù)據(jù)做處理，#表示退格鍵，刪除#前的一個(gè)字符。@表示@符號(hào)之前的數(shù)據(jù)均無效。

比如用戶輸入了 gosd##od實(shí)際有效字符是good，當(dāng)用戶輸入了pgm@progre#am實(shí)際有效的是program。

思路分析

將一行的字符依次讀入棧中，遇到#取出棧頂數(shù)據(jù)，若遇到@則清空棧。

實(shí)現(xiàn)

import java.util.Arrays;
import java.util.Stack;
import java.util.stream.Collectors;

/**
 * 行編輯器
 *
 * @author jaune
 */
public class LineEditor {

    public String handle(String line) {
        char[] chars = line.toCharArray();
        Stack<Character> stack = new Stack<>();
        for (char ch : chars) {
            if (stack.isEmpty()) {
                if (ch != '#' && ch != '@') {
                    stack.push(ch);
                }
            } else {
                if (ch == '#') {
                    stack.pop();
                } else if (ch == '@') {
                    stack.clear();
                } else {
                    stack.push(ch);
                }
            }
        }
        Character[] res = new Character[stack.size()];
        stack.toArray(res);
        stack.clear();
        return Arrays.stream(res).map(String::valueOf).collect(Collectors.joining());
    }
}