关于使用栈解决括号匹配的问题

忘是亡心i 2022-09-17 13:22 130阅读 0赞

封装好的类:

1-->public Stack()创建一个空堆栈

2-->public boolean empty()测试堆栈是否为空;

3-->public E pop()移除堆栈顶部的对象，并作为此函数的值返回该对象。

4-->public E push(E item)把项压入堆栈顶部

5-->public E peek()查看堆栈顶部的对象，但不从堆栈中移除它。

6-->public boolean empty()测试堆栈是否为空

## 括号配对问题 ##

描述

现在，有一行括号序列，请你检查这行括号是否配对。

输入

第一行输入一个数N（0<N<=100）,表示有N组测试数据。后面的N行输入多组输入数据，每组输入数据都是一个字符串S(S的长度小于10000，且S不是空串），测试数据组数少于5组。数据保证S中只含有"\[","\]","(",")"四种字符

输出

每组输入数据的输出占一行，如果该字符串中所含的括号是配对的，则输出Yes,如果不配对则输出No

代码：

package com.accp;  
import java.util.ArrayList;  
import java.util.List;  
/\*\*  
 \* 栈 (Stack, 先进后出(FILO)的数据结构)  
 \* @author Administrator  
 \*  
 \* @param <T> 栈存储的数据类型的泛型参数  
 \*/  
public class MyStack<T> \{  
private List<T> list = new ArrayList<T>();  
  
/\*\*  
\* 入栈  
\*/  
public void push(T element) \{  
list.add(element);  
\}  
  
/\*\*  
\* 出栈  
\* @return  
\*/  
public T pop() \{  
return list.remove(list.size() - 1);  
\}  
  
  
/\*\*  
\* 判断栈是否为空  
\* @return true-空, false-非空  
\*/  
public boolean isEmpty() \{  
return list.size() == 0;  
\}  
  
/\*\*  
\* 获取栈的大小  
\* @return 栈的大小  
\*/  
public int size() \{  
return list.size();  
\}  
\}

package com.accp;  
public class Test01 \{  
  
  
public static void main(String\[\] args) \{  
System.out.println(checkBrace("\[(2+3) \* 5\] + 9"));  
System.out.println(checkBrace("\{2 + ( 3 \* 5\} – 6)"));  
System.out.println(checkBrace("(2+3)) \* 5"));  
\}  
  
/\*\*  
\* 检查括号是否匹配  
\* @return true-匹配, false-不匹配  
\*/  
public static boolean checkBrace(String str) \{  
MyStack<Character> stack = new MyStack<Character>();  
  
for(int i = 0; i < str.length(); i++) \{  
char ch = str.charAt(i);  
if(ch == '(' || ch == '\[' || ch == '\{') \{  
stack.push(ch); // 遇到左括号 - 入栈  
\}  
else if(ch == ')' || ch == '\}' || ch == '\]') \{  
// 遇到右括号 - 出栈  
if(! stack.isEmpty()) \{ // 栈不为空  
char temp = stack.pop();  
if(!(ch == ')' && temp == '(') &&  
!(ch == '\]' && temp == '\[') &&  
!(ch == '\}' && temp == '\{')) \{  
return false;  // 左右括号没有匹配上  
\}  
\}  
else \{ // 栈为空说明有右括号但没有左括号与之匹配  
return false;  
\}  
\}  
\}  
  
// 此时如果栈不为空则说明有左括号而与之匹配的右括号  
return stack.isEmpty();  
\}  
\}