注:下文代码主要来自参考书籍,本人稍稍修改了一下。
泛型栈类:
package com.heyang;
/**
* 栈数据结构
* 说明:
* 作者:何杨(heyang78@gmail.com)
* 创建时间:2011-1-15 上午07:51:09
* 修改时间:2011-1-15 上午07:51:09
*/
public class MyStack<T>{
private int size; // 大小
private T[] datas; // 数据
private int top; // 栈顶元素下标
@SuppressWarnings("unchecked")
public MyStack(int size){
this.size=size;
datas= (T[])new Object[this.size];
top=-1;
}
/**
* 压栈
*/
public void push(T t){
datas[++top]=t;
}
/**
* 出栈
*
* 说明:
* @return
* 创建时间:2011-1-15 上午08:01:15
*/
public T pop(){
return datas[top--];
}
/**
* 取得栈顶元素
*
* 说明:
* @return
* 创建时间:2011-1-15 上午08:02:02
*/
public T getTopItem(){
return datas[top];
}
/**
* 查看栈是否为空
*
* 说明:
* @return
* 创建时间:2011-1-15 上午08:02:38
*/
public boolean isEmpty(){
return top==-1;
}
}
括号检查类:
package com.heyang;
/**
* 表达式中括号检查类
* 说明:
* 作者:何杨(heyang78@gmail.com)
* 创建时间:2011-1-15 上午08:05:25
* 修改时间:2011-1-15 上午08:05:25
*/
public class BracketChecker{
private String input; // 输入:待检查的表达式
private boolean isValid; // 是否检查通过
private String checkResult; // 输出:检查结果
/**
* 构造函数
* @param input
*/
public BracketChecker(String input){
this.input=input;
this.isValid=false;
this.checkResult="";
check();
}
/**
* 执行检查
*
* 说明:
* 创建时间:2011-1-15 上午08:09:25
*/
private void check(){
int length=input.length();
MyStack<Character> stack=new MyStack<Character>(length);
for(int i=0;i<length;i++){
char c=input.charAt(i);
switch(c){
case '{':
case '[':
case '(':
stack.push(c);
break;
case '}':
case ']':
case ')':
if(stack.isEmpty()==false){
char top=stack.pop();
if( (c=='}' && top!='{') || (c==']' && top!='[') || (c==')' && top!='(') ){
isValid=false;
checkResult="经检查,表达式'"+input+"'中,位于第"+(i+1)+"的字符‘"+c+"’没有对应的匹配项";
return;
}
}
else{
isValid=false;
checkResult="经检查,表达式'"+input+"'中,位于第"+(i+1)+"的字符‘"+c+"’没有对应的匹配项";
return;
}
break;
default:
break;
}
}
if(stack.isEmpty()==false){
isValid=false;
checkResult="经检查,表达式'"+input+"'中右括号缺失,匹配不完整";
return;
}
else{
isValid=true;
checkResult="经检查,表达式'"+input+"'中括号匹配无误.";
return;
}
}
/**
* 括号是否匹配
*
* 说明:
* @return
* 创建时间:2011-1-15 上午08:39:38
*/
public boolean isValid() {
return isValid;
}
/**
* 取得检查结果
*
* 说明:
* @return
* 创建时间:2011-1-15 上午08:39:27
*/
public String getCheckResult() {
return checkResult;
}
public static void main(String[] args){
String[] arr={"1+(2/3-4","[1+(2/3-4)]*5","{[1+(2/3-4)]*5+(6+2*3)}*7","{[1+(2/3-4]*5+(6+2*3)}*7"};
for(String str:arr){
BracketChecker c=new BracketChecker(str);
System.out.println(c.getCheckResult());
}
}
}
检查结果:
经检查,表达式'1+(2/3-4'中右括号缺失,匹配不完整
经检查,表达式'[1+(2/3-4)]*5'中括号匹配无误.
经检查,表达式'{[1+(2/3-4)]*5+(6+2*3)}*7'中括号匹配无误.
经检查,表达式'{[1+(2/3-4]*5+(6+2*3)}*7'中,位于第11的字符‘]’没有匹配项
参考书籍:SAMS的《Java数据结构与算法》第四章