堆栈应用——括号匹配问题

堆栈是各种软件系统中应用最广泛的数据结构之一。括号匹配问题和表达式计算是编译软件中的基本问题，其软件设计中都需要用到堆栈。

【括号匹配问题】

　　假设一个算术表达式中包含圆括号、方括号和花括号三种类型括号，编写一个判别表达式中括号是否正确匹配配对的函数，并设计一个测试主函数。

【设计分析】 括号匹配后到的括号要最先被匹配，满足堆栈“后进先出”的操作特点。

　　括号匹配有以下4种情况：

　　（1）左右括号配对次序不正确；

　　（2）右括号多于左括号；

　　（3）左括号多于右括号；

　　（4）括号匹配正确。

【源代码】

SeqStackTest.java

1 package seqstack;
 2 
 3 public class SeqStackTest { 
 4     //遍历字符数组并利用进栈出栈匹配括号  
 5     static void expIsCorrect(String[] exp,int n)throws Exception{  
 6         SeqStack myStack = new SeqStack(100);  
 7         //LinStack myStack = new LinStack(); //也可以用链式堆栈  
 8         for(int i=0;i<n;i++){//如果是左括号就入栈  
 9             if((exp[i].equals(new String("(")))  
10                     || (exp[i].equals(new String("[")))  
11                     || (exp[i].equals(new String("{"))))  
12                 myStack.push(exp[i]);  
13             //如果是右括号）并且和栈顶（匹配，出栈  
14             else if((exp[i].equals(new String(")"))) && myStack.notEmpty()  
15                     && myStack.getTop().equals(new String("(")))  
16                 myStack.pop();  
17             //遍历的右括号)和栈顶不匹配，说明公式错误，结束遍历  
18             else if((exp[i].equals(new String(")"))) && myStack.notEmpty()  
19                     && !myStack.getTop().equals(new String("("))){  
20                 System.out.println("左右括号匹配次序不正确！");  
21                 return;  
22             }  
23             //如果是右括号]并且和栈顶[匹配，出栈  
24             else if((exp[i].equals(new String("]"))) && myStack.notEmpty()  
25                     && myStack.getTop().equals(new String("[")))  
26                 myStack.pop();  
27             //遍历的右括号]和栈顶不匹配，说明公式错误，结束遍历  
28             else if((exp[i].equals(new String("]"))) && myStack.notEmpty()  
29                     && !myStack.getTop().equals(new String("["))){  
30                 System.out.println("左右括号匹配次序不正确！");  
31                 return;  
32             }  
33             //如果是右括号}并且和栈顶{匹配，出栈  
34             else if((exp[i].equals(new String("}"))) && myStack.notEmpty()  
35                     && myStack.getTop().equals(new String("{")))  
36                 myStack.pop();  
37             //遍历的右括号}和栈顶不匹配，说明公式错误，结束遍历  
38             else if((exp[i].equals(new String("}"))) && myStack.notEmpty()  
39                     && !myStack.getTop().equals(new String("{"))){  
40                 System.out.println("左右括号匹配次序不正确！");  
41                 return;  
42             }  
43             //如果栈已空，但还存在右括号，说明右括号多了  
44             else if((exp[i].equals(new String(")")))  
45                     || (exp[i].equals(new String("]")))  
46                     || (exp[i].equals(new String("}")))  
47                     && !myStack.notEmpty()){  
48                 System.out.println("右括号多余左括号!");  
49                 return;  
50             }  
51         }  
52         //遍历完成后栈内还有元素，说明左括号多了  
53         if(myStack.notEmpty())  
54             System.out.println("左括号多余右括号!");  
55         else  
56             System.out.println("括号匹配正确！");  
57     }  
58       
59     private static String[] strToString(String str){//把字符串转换为String类型数组  
60         //为什么不转换为字符数组char[]呢?  
61         //因为只有String类型的数据才具有可比性，也就是能用equals  
62         int n = str.length();  
63         String[] a = new String[n];  
64         for(int i=0;i<n;i++){  
65             a[i] = str.substring(i,i+1);//取子串含头不含尾，故可以取出i位置的字符并返回字符串类型  
66         }  
67         return a;  
68     }  
69       
70     public static void main(String[] args) {  
71         String str;  
72         int n;  
73         try{  
74             str = "(())abc{[}(){";//左右括号匹配次序不正确  
75             n = str.length();  
76             String[] a = strToString(str);  
77             expIsCorrect(a,n);  
78               
79             str = "(()))abc{[]}";//右括号多余左括号  
80             n = str.length();  
81             String[] b = strToString(str);  
82             expIsCorrect(b,n);  
83               
84             str = "(()()abc{[]}";//左括号多余右括号  
85             n = str.length();  
86             String[] c = strToString(str);  
87             expIsCorrect(c,n);  
88               
89             str = "(())abc{[]}";//括号匹配正确！  
90             n = str.length();  
91             String[] d = strToString(str);  
92             expIsCorrect(d,n);  
93         }  
94         catch(Exception e){  
95             System.out.println(e.getMessage());  
96         }  
97   
98     }  
99 }

Stack.java

1 package seqstack;
2 
3 public interface Stack {
4     public void push(Object obj)throws Exception;
5     public Object pop()throws Exception;
6     public Object getTop()throws Exception;
7     public boolean notEmpty();
8 }

SeqStack.java

package seqstack;

public class SeqStack implements Stack{
    final int defaultSize=10;
    int top;
    Object[] stack;
    int sizeMaxSize;
    
    public SeqStack(int sz)
    {
        initiate(sz);
    }

    private void initiate(int sz) {
        // TODO Auto-generated method stub
        sizeMaxSize=sz;
        top=0;
        stack=new Object[sz];
    }
    
    public void push(Object obj)throws Exception{
        if(top == sizeMaxSize)
        {
            throw new Exception("堆栈已满！");
        }
        stack[top] = obj;
        top++;
    }
    
    public Object pop()throws Exception{
        if(top == 0)
        {
            throw new Exception("堆栈已空！");
        }
        top--;
        return stack[top];
    }
    
    public Object getTop()throws Exception{
        if(top == 0)
        {
            throw new Exception("堆栈已空！");
        }
        return stack[top-1];
    }
    public boolean notEmpty(){
        return(top>0);
    }
    
    
}

【运行结果】