用栈实现括号匹配

用栈!


题:队列与栈_栈结构的应用
栈结构很有用处,有时通过它可以轻松化解一些难题。

看如下问题:

...(.[...)...]...(..(.)..)..{..}.[.]...[[...(.).]..].

请判断一个串中的括号是否匹配
注意下列不匹配的情况:

左括号太多
右括号太多
右括号先于左括号出现 ..)...(...
挎臂情况 ....[...(....]....)....

考虑用栈

用 Stack 的 pop 和 push 匹配括号,为方便,初始状况下在字符串左右加一对括号。
源码BRKT.java


package BRKT;
import java.util.Stack;

public class Match {
    public static boolean match(String x) {
        x = "(" + x + ")";
        Stack<String> stk = new Stack<String>();
        String[] a = x.split("");
        boolean flag = true;
        for (int i=0; i<a.length && flag; i++) {
            switch (a[i]) {
            case "(":
                stk.push(a[i]);
                break;
            case ")":
                if (stk.peek().equals("(")) {
                    stk.pop();
                }
                else {
                    flag = false;
                }
                break;
            case "[":
                stk.push(a[i]);
                break;
            case "]":
                if (stk.peek().equals("[")) {
                    stk.pop();
                }
                else {
                    flag = false;
                }
                break;
            case "{":
                stk.push(a[i]);
                break;
            case "}":
                if (stk.peek().equals("{")) {
                    stk.pop();
                }
                else {
                    flag = false;
                }
                break;
            }
        }
        if (flag) {
            if (stk.empty()) {
                return true;
            }
            else {
                return false;
            }
        }
        else {
            return false;
        }
    }
}


references——
csdnBlog

发表评论

电子邮件地址不会被公开。 必填项已用*标注