这篇文章讲述的是数据结构部分的括号匹配算法的java实现，如有错误或者不当之处，还望各位大神批评指正。

问题描述

假设一个表达式中允许包含两种括号圆括号()和方括号[]，其嵌套的顺序随意，及()等正确格式，[(]等不正确格式，编写一个算法来判断输入的格式是否正确。

算法分析

1. 可以使用char类型的数组来存放括号
2. 借助栈，当为左括号时入栈，为右括号时若与栈顶匹配则出栈
3. 若最后栈为空则匹配成功，否则匹配失败

代码实现

• 注：栈的实现详见https://blog.csdn.net/u013634252/article/details/81304067，这里不再赘述

package stack_question;import java.util.Scanner;import stack.LinkStack;
import stack.SeqStack;
import stack.Stack;/*** @author 叶清逸* @date 2018年7月31日下午3:22:46* @version 1.0* @project stack_question*/
public class Q1_ParenthesisMatching {/*** 问题分析：假设一个表达式中允许包含两种括号圆括号()和方括号[]，其嵌套的顺序随意，及([]())等正确格式，[(]等不正确*          格式，编写一个算法来判断输入的格式是否正确。* * 算法分析：1. 可以使用char类型的数组来存放括号*          2. 借助栈，当为左括号时入栈，为右括号时若与栈顶匹配则出栈*          3. 若最后栈为空则匹配成功，否则匹配失败*/public static void main(String[] args) {/*读取键盘输入的括号，存入数组*/System.out.println("请输入要匹配的括号'()'或'[]'串,无分隔符：");Scanner s = new Scanner(System.in) ;String arr = s.nextLine() ;s.close();/*判断是否匹配*/boolean flag = isMarth(arr.toCharArray()) ;/*输出结果*/if(flag == true)System.out.println("匹配成功");else System.out.println("匹配失败");}private static boolean isMarth(char [] arr){/*创建辅助栈*/Stack stack = new LinkStack() ;stack.init();/*遍历数组进行判断*/for(int i=0 ; i<arr.length ; ++i){/*取出元素*/char c = arr[i] ;/*判断若与栈顶元素匹配则出栈，否则入栈*/if(stack.getTop() == null){stack.push(c);}else{char top = (char)stack.getTop() ;if(top == '(' && c == ')'){stack.pop() ;}else if(top == '[' && c == ']'){stack.pop() ;}else{stack.push(c);}}}return stack.isEmpty() ;}
}

样例输出

• 样例输入

请输入要匹配的括号'()'或'[]'串,无分隔符：
()[]()

• 样例输出

匹配成功