我们经常在各种 IDE(集成开发环境)中敲代码.
现在的 IDE 非常智能, 并会给出相应提示, 还有及时的错误提醒.
其中有一项就是括号匹配的检测.
今天我们来谈一谈其中的原理.
先上图
图片发自简书 App
再上代码
- import java.io.BufferedReader;i
- mport java.io.InputStreamReader;
- import java.util.Scanner;
- class Stack{
- char [] data; int maxSize;// 数组的长度 int top; Scanner input=new Scanner(System.in); public Stack(int maxSize) { this.maxSize=maxSize; data=new char[maxSize]; top=-1;
- /* 注意: 因为数组下标是从 0 开始的, 一开始 top 为 - 1 就表示栈为空.*/
- }
- public int getSize()
- {
- return maxSize;
- }
- public int getElementCount()
- {
- // 得到栈顶元素标号
- return top;
- }
- public boolean isEmpty()
- // 判断是否为空栈 {
- return top==-1;
- }
- public boolean isFull()
- {
- return top+1==maxSize;
- // 数组下标从 0 开始, 所以这里 top 要先加 1
- } public boolean push(char data)
- {
- if(isFull()) {
- System.out.println("栈已满");
- return false;
- }
- this.data[++top]=data;/* 这里的表达式 (++top) 的值是原来 top+1 并且 top 的值从此已经加 1, 因为已经入栈了一次.*/ return true;
- }
- public char pop() throws Exception
- { if(isEmpty())
- {
- throw new Exception("栈已空");
- }
- return this.data[top--];/* 这里 (top--) 的值仍然是原来 top 的值, 并且从此 top 的值已经减 1. 因为已经弹栈了一次.*/
- } public char peek()
- {// 查看当前栈顶元素 return this.data[getElementCount()];
- }
- public void pipei() throws Exception { char ch,temp;
- // 定义输入的字符和接收弹出的字符变量 int match;// 是否匹配的标志 BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
- ch=(char)reader.read();
- while(ch!='0')
- {
- if(getElementCount()==-1)
- {
- push(ch);
- } else {
- temp=pop();// 取出栈顶元素
- match=0;
- if(temp=='('&&ch==')')
- {
- match=1;
- }
- if(temp=='<'&&ch=='>')
- { match=1; }
- if(temp=='{'&&ch=='}')
- { match=1; }
- if(temp=='['&&ch==']')
- { match=1; }
- if(match==0)
- { push(temp); push(ch); }
- /* 注意, 如果 match 为 1, 那么被取出的栈顶元素是不会被重新入栈的.*/
- }
- ch=(char)reader.read();
- }
- if(getElementCount()==-1)
- {
- System.out.println("匹配!");
- /*while 循环结束后, 判断栈是否为空, 若为空说明每次取出栈顶的元素都与输入的括号相匹配 */}
- else
- { System.out.println("不匹配!");
- }
- }
- }
- public class bracketsMatchAlrogithm { /* 这里为了简单, 就直接在主函数中抛出异常, 实际中不要这么做.*/ public static void main(String[] args) throws Exception{ String go; Scanner input=new Scanner(System.in); Scanner input2=new Scanner(System.in); System.out.println("请输入最大字符容量"); Stack s=new Stack(input.nextInt()); System.out.println("括号匹配"); do { System.out.println("请输入一组括号组合, 以 0 表示结束"); s.pipei(); System.out.println("继续?(y/n)"); go=input.nextLine(); }while(go.equalsIgnoreCase("y")); System.out.println("游戏结束"); input.close(); input2.close(); } }
以上内容是本人学习之后的总结, 注释和画图均为本人所做, 画图技术不好... 难免粗糙, 体谅一下, 嘿嘿.
另外, 本人水平有限, 难免有缺漏和不足, 望各位大侠指出啊! thankyou very much
来源: http://www.jianshu.com/p/871df2d5c03d