题目：判定字符串中开闭分隔符是否匹配
思路：
1.分解字符串成字符数组，并创建一个栈
2.如果读取的字符不是开闭分隔符，直接忽略
如果读取的字符是开分隔符则压栈
如果读取的字符是闭分隔符，且栈不为空，栈顶元素出栈，否则提示匹配错误
3.如果出栈的开分隔符与读取的闭分隔符不匹配，提示匹配错误
4.字符串处理完后，如果栈不为空，则提示匹配错误
/**
* 判定字符串中开闭分隔符是否匹配
* @param string 需要判断的字符串
* @return true 分隔符匹配 false 分隔符不匹配
*/
public static boolean isMatch(String string) {
// 1.将字符串转换成字符数组
char[] chars = string.toCharArray();
// 2.创建一个字符栈
LinkedListStack<Character> stack = new LinkedListStack<Character>();
// 3.遍历字符数组
for (int i = 0; i < chars.length; i++) {
// 3.1 如果为开分隔符则压栈
if ('(' == chars[i] || '{' == chars[i] || '[' == chars[i]) {
stack.push(chars[i]);
}
// 3.2 如果为闭分隔符且栈不为空则出栈，否则提示匹配错误
if (')' == chars[i] || '}' == chars[i] || ']' == chars[i]) {
if (stack.isEmpty()) {
System.out.println("开闭分隔符不匹配！缺少与" + chars[i] + "对应的分隔符");
return false;
} else {
// 栈不为空时，判断出栈的字符是不是匹配的开分隔符
char temp = stack.pop();
switch (chars[i]) {
case ']':
if ('[' != temp) {
System.out.println("开闭分隔符不匹配！缺少与" + chars[i] + "对应的分隔符");
return false;
}
break;
case '}':
if ('{' != temp) {
System.out.println("开闭分隔符不匹配！缺少与" + chars[i] + "对应的分隔符");
return false;
}
break;
case ')':
if ('(' != temp) {
System.out.println("开闭分隔符不匹配！缺少与" + chars[i] + "对应的分隔符");
return false;
}
break;
default:
break;
}
}
}
}
// 4.字符数组处理完，如果栈不为空，说明栈内有多余的开分隔符，提示匹配出错
if (!stack.isEmpty()) {
System.out.println("开闭分隔符不匹配！缺少与" + stack.top() + "对应的分隔符");
return false;
}
return true;
}
题目：中缀表达式转换成后缀表达式
性质：观察中缀表达式2+3*4和后缀表达式234*+
两种表达式的操作数次序相同，但操作符不同
思路：
1.栈中只存储"("和运算符
2.在遇到")"时，从栈中弹出运算符，直到"("出栈；但"("不输出
3.在比较运算符优先级时，只要栈顶运算符优先级不低于读取的运算符，就出栈
4.要保证栈最后为空
/**
* 中缀表达式转换成后缀表达式
* @param infix 中缀表达式
* @return 后缀表达式
*/
public static String infixToPostfix(String infix) {
// 1.将表达式转换成字符数组
char[] chars = infix.toCharArray();
// 2.后缀表达式
StringBuffer postfix = new StringBuffer();
// 3.创建一个字符栈，栈里面只存储"("和运算符
LinkedListStack<Character> stack = new LinkedListStack<Character>();
// 4.遍历字符数组
for (int i = 0; i < chars.length; i++) {
switch (chars[i]) {
case '(':
case '+':
case '-':
case '*':
case '/':
if (!stack.isEmpty() && compare(stack.top(), chars[i])) {
postfix.append(stack.pop());
}
stack.push(chars[i]);
break;
case ')':
while (stack.top() != '(') {
postfix.append(stack.pop());
}
// 将"("弹出
stack.pop();
break;
default:
postfix.append(chars[i]);
break;
}
}
// 5.字符数组遍历完，如果栈不为空，说明栈内还有运算符
while (!stack.isEmpty()) {
postfix.append(stack.pop());
}
return postfix.toString();
}
/**
* 运算符比较优先级
* @param stackSymbol 栈中运算符
* @param symbol 读取的运算符
* @return true 栈中优先级高 false 读取的运算符优先级高
*/
public static boolean compare(char stackSymbol, char symbol) {
int priorityOfStack = OperatorEnum.priorityOf(stackSymbol);
int priorityOfSymbol = OperatorEnum.priorityOf(symbol);
if ((priorityOfStack - priorityOfSymbol) >= 0) {
// 如果读取的字符为"("，直接压入栈
if (priorityOfSymbol == 0) {
return false;
}
return true;
}
return false;
}
运算符以及其优先级通过枚举类型实现，如下：
public enum OperatorEnum {
PLUS('+',1), MINUS('-',1), MULTI('*',2), DIVIDE('/',2), OPENPAREN('(',0);
private Character operator;
private int priority;
private OperatorEnum(Character operator, int priority) {
this.operator = operator;
this.priority = priority;
}
/**
* 获取运算符的对应优先级
* @param operator 运算符
* @return 对应的优先级
*/
public static int priorityOf(char operator) {
for (OperatorEnum oper : values()) {
if (oper.getOperator() == operator) {
return oper.getPriority();
}
}
return operator;
}
/**
* @return the operator
*/
public Character getOperator() {
return operator;
}
/**
* @param operator the operator to set
*/
public void setOperator(Character operator) {
this.operator = operator;
}
/**
* @return the priority
*/
public int getPriority() {
return priority;
}
/**
* @param priority the priority to set
*/
public void setPriority(int priority) {
this.priority = priority;
}
}