java设计一个算法利用栈检查用户输入的表达式中括号是否配对(假设表达式中可能含有圆括号、中括号和大括号),并用相关数据进行测试。要求:栈使用自建的结构,顺序栈和链栈皆可。
时间: 2024-10-27 13:10:44 浏览: 26
设计一个算法判别一个算术表达式的圆括号是否正确配对
在Java中,你可以设计一个简单的算法来检查表达式中的括号是否配对,这通常通过使用栈的数据结构来完成。这里我会提供一种基于顺序栈的解决方案。首先,定义一个Stack类,包含push(压入)、pop(弹出)和isEmpty(判断栈是否为空)等基本操作。
```java
public class Stack {
private int[] elements;
private int top;
// 初始化栈
public Stack(int capacity) {
elements = new int[capacity];
top = -1;
}
// 判断栈是否为空
public boolean isEmpty() {
return top == -1;
}
// 压入元素
public void push(int item) {
if (top < elements.length - 1) {
top++;
elements[top] = item;
} else {
System.out.println("Stack is full.");
}
}
// 弹出元素
public int pop() {
if (!isEmpty()) {
int item = elements[top];
top--;
return item;
} else {
throw new EmptyStackException();
}
}
}
// 检查括号匹配的函数
public boolean checkParentheses(String expression, String supportedChars) {
Stack stack = new Stack(supportedChars.length());
for (char c : expression.toCharArray()) {
if (supportedChars.contains(String.valueOf(c))) {
stack.push(c);
} else if (c == ')' || c == ']' || c == '}') {
char openBracket = stack.pop();
if (c != ')' && openBracket != '(' ||
c != ']' && openBracket != '[' ||
c != '}' && openBracket != '{') {
return false; // 匹配错误
}
} else {
System.out.println("Invalid character in expression.");
return false;
}
}
return stack.isEmpty(); // 如果最终栈为空,表示所有括号都已配对
}
```
为了验证这个算法,你可以创建一些测试用例:
```java
public static void main(String[] args) {
System.out.println(checkParentheses("({[()]})", "()" + "{}" + "[" + "]")); // true
System.out.println(checkParentheses("({[()]])", "()" + "{}" + "[" + "]")); // false (右括号多一个)
System.out.println(checkParentheses("(]", "()" + "{}" + "[" + "]")); // false (缺少左方括号对应)
System.out.println(checkParentheses("{[}", "()" + "{}" + "[" + "]")); // false (缺少左花括号对应)
}
```
阅读全文