接下篇：http://www.cnblogs.com/fuck1/p/5995857.html
堆栈的应用1：括号匹配算法
括号匹配问题
假设算术表达式中包含圆括号，方括号，和花括号三种类型。使用栈数据结构编写一个算法判断表达式中括号是否正确匹配，并设计一个主函数测试。
比如：{a+[b+(c*a)/(d-e)]} 正确
([a+b)-(c*e)]+{a+b} 错误
对于表达式中的括号是否匹配，不能仅仅通过统计左括号'('出现的次数和右括号')'出现的次数是否相等来实现，“a*)b+c(”这样的表达式中的括号显然是不匹配的。检验括号是否匹配最常见的方法是借助于栈这种数据结构，从左到右逐个字符扫描表达式，碰到左括号"("则压入栈中(push)，碰到右括号")"则弹出栈顶元素(pop)如果栈为空，则匹配失败。字符串扫描完成后，如果栈为空，则匹配成功，否则匹配失败。
//-------------------------------------------------------------在这里虽然Java给出了Stack的类但是还是自定义
//下面是一个stack接口的定义
//栈接口
public interface Stack { // 入栈
public void push(Object obj) throws Exception; // 出栈
public Object pop() throws Exception; // 获得栈顶元素
public Object getTop() throws Exception; // 判断栈是否为空
public boolean isEmpty();
}
Stack interface
//顺序栈的具体实现，通过数组实现
//顺序栈
public class SequenceStack implements Stack {
Object[] stack; // 对象数组
final int defaultSize = 10; // 默认长度
int top;// 栈顶位置
int maxSize;// 最大长度
public SequenceStack() {
// 默认方法初始化
init(defaultSize);
}
// 显示调用方法初始化
public SequenceStack(int size) {
// 根据用户传入的参数进行初始化
init(size);
}
// 初始化方法
private void init(int size) {
this.maxSize = size;
top = 0;
stack = new Object[size];
}
// 入栈操作
@Override
public void push(Object obj) throws Exception {
// TODO Auto-generated method stub
// 判断栈是否已满
if (top == maxSize) {
throw new Exception("堆栈已满");
}
// 入栈
stack[top] = obj;
top++;
}
// 出栈
@Override
public Object pop() throws Exception {
// TODO Auto-generated method stub
// 判断栈是否为空
if (isEmpty()) {
throw new Exception("堆栈为空！");
}
// 因为在入栈之后默认将top值进行了++所以导致不指示当前位置
top--;
return stack[top];
}
// 获得栈顶元素
@Override
public Object getTop() throws Exception {
// TODO Auto-generated method stub
if (isEmpty()) {
throw new Exception("堆栈为空！！");
}
// 单纯获得栈顶元素
return stack[top - 1];
}
@Override
public boolean isEmpty() {
// TODO Auto-generated method stub
return top == 0;
}
}
//获得栈的具体使用操作后，下面使用堆栈完成对括号匹配算法的使用:
import java.util.Scanner; //平衡符号算好，检查算数式的括号是否是正确的，小括号，中括号，大括号
public class Test {
public static void main(String[] args) throws Exception {
String str = "{a + [b + ( c * a ) / ( d * e)]}";
String str2 = "{a+(a*B)+[a-1] + }"; signCheck(str2);
} // 字符串检查
public static void signCheck(String str) throws Exception {
SequenceStack stack = new SequenceStack();
String[] arr = expToStringArray(str);
for (int i = 0; i < arr.length; i++) {
// 如果数组中有这三种左括号元素那么直接进行入栈操作
if (arr[i].equals("(") || arr[i].equals("[") || arr[i].equals("{")) {
stack.push(arr[i]);
} else if (arr[i].equals(")") && !stack.isEmpty()
&& stack.getTop().equals("(")) {
// 上面的if判断主要是当我们遇到右括号时，发现当前位于栈顶的是左括号，那么此时可以出栈了
stack.pop();
} else if (arr[i].equals(")") && !stack.isEmpty()
&& !stack.getTop().equals("(")) { System.out.println("左右括号匹配次序不成功");
return;
}
// 遇到中括号时
else if (arr[i].equals("]") && !stack.isEmpty()
&& stack.getTop().equals("[")) {
// 上面的if判断主要是当我们遇到右括号时，发现当前位于栈顶的是左括号，那么此时可以出栈了
stack.pop();
} else if (arr[i].equals("]") && !stack.isEmpty()
&& !stack.getTop().equals("[")) { System.out.println("左右括号匹配次序不成功");
return;
} // 大括号匹配
else if (arr[i].equals("}") && !stack.isEmpty()
&& stack.getTop().equals("{")) {
// 上面的if判断主要是当我们遇到右括号时，发现当前位于栈顶的是左括号，那么此时可以出栈了
stack.pop();
} else if (arr[i].equals("}") && !stack.isEmpty()
&& !stack.getTop().equals("{")) { System.out.println("左右括号匹配次序不成功");
return;
} // 右括号多于左括号的情况
else if (arr[i].equals(")") || arr[i].equals("]")
|| arr[i].equals("}") && stack.isEmpty()) {
System.out.println("右括号多于左括号");
return;
}
}
// 经历完一趟循环后如果堆栈不为空，那么左括号就多了
if (!stack.isEmpty()) {
System.out.println("左括号多于右括号");
} else {
System.out.println("匹配正确");
} } // 字符串转为字符串数组
public static String[] expToStringArray(String exp) {
// 字符串数组长度
int n = exp.length();
String[] arr = new String[n];
for (int i = 0; i < n; i++) {
arr[i] = exp.substring(i, i + 1);
} return arr;
}
}