栈是嵌套调用机制的实现基础
使用栈以非递归方式实现递归算法
判断表达式中圆括号是否匹配 package pers.zhang.stack;/** * @author zhang * @date 2020/1/16 - 14:42 * * 栈应用：括号匹配 */public class Exp_bracket { //判断expstr表达式中的圆括号是否匹配，若匹配，返回空串，否则返回错误信息 public static String isValid(String expstr){ SeqStack<String> stack = new SeqStack<String>(expstr.length()); //顺序栈 for (int i = 0; i < expstr.length(); i++){ char ch = expstr.charAt(i); switch(ch){ case '(': stack.push(ch + "");//左括号入栈 break; case ')': if (stack.isEmpty() || !stack.pop().equals("(")) //遇见右括号时，出栈 return "期望(";//判断出栈字符是否为左括号 } } return (stack.isEmpty()) ? "" : "期望)"; //返回空串表示没有错误 } public static void main(String args[]) { String expstr = "((1+2)*3+4)"; System.out.println(expstr + " " + isValid(expstr)); }}/*程序多次运行时，若expstr分别表示不同的表达式字符串，运行结果如下：((1+2)*3+4) ((1+2)*3+4 期望)((1+2)*3+4))( 期望(*/ 使用栈计算表达式值
1.将中缀表达式转换为后缀表达式
2.后缀表达式求值
```java
package pers.zhang.stack;
/**
@author zhang
@date 2020/1/16 - 14:52
栈应用：表达式求值
*/
public class Expression {
//返回expstr的后缀表达式
public static String toPostfix(String expstr){
SeqStack stack = new SeqStack(expstr.length()); //创建运算符栈，顺序栈
String postfix = “”;//记载后缀表达式
int i = 0;
while (i < expstr.length())
{
char ch = expstr.charAt(i);
switch (ch){
case ‘+’: //遇到＋、－运算符，与栈顶元素比较
case ‘-’:
while (!stack.isEmpty() && !stack.get().equals("("))
postfix += stack.pop();
stack.push(ch + “”); //当前运算符入栈
i++;
break;
case '’: //遇到、/ 运算符
case ‘/’:
while (!stack.isEmpty() && (stack.get().equals("*") || stack.get().equals("/")))
postfix += stack.pop();
stack.push(ch+"");
i++;
break;
case ‘(’:
stack.push(ch + “”); //遇到左括号，入栈
i++;
break;
case ‘)’:
String out = stack.pop(); //遇到右括号，出栈，若栈空返回null
while (out!=null && !out.equals("(")){ //判断出栈字符是否为左括号
postfix += out;
out = stack.pop();
}
i++; break;
default:
while (i<expstr.length() && ch>=‘0’ && ch<=‘9’){ //遇到数字时，加入到后缀表达式
postfix += ch;
i++;
if (i < expstr.length())
ch = expstr.charAt(i);
}
postfix += " "; //添加空格作为数值之间的分隔符
}
}
while (!stack.isEmpty())
postfix += stack.pop();
return postfix;
}
//计算后缀表达式的值
public static int value(String postfix){
LinkedStack stack = new LinkedStack(); //创建操作数栈，链式栈
int i = 0, result = 0;
while (i < postfix.length()){ //逐个检查后缀表达式中的字符
char ch = postfix.charAt(i);
if (ch >= ‘0’ && ch <= ‘9’){ //遇到数字字符
result = 0;
while (ch != ’ '){ //字符串转化为数值
result = result * 10 + Integer.parseInt(ch + “”);
i++;
ch = postfix.charAt(i);
}
i++;
stack.push(new Integer(result)); //操作数入栈
}else{
int y = stack.pop().intValue(); //出栈两个操作数
int x = stack.pop().intValue();
switch (ch){ //根据运算符分别计算
case ‘+’:
result = x + y;
break;
case ‘-’:
result = x - y;
break;
case ‘*’:
result = x * y;
break;
case ‘/’:
result = x / y;
break; //整除，除数为0时将抛出异常
}
stack.push(new Integer(result)); //运算结果入栈
i++;
}
}
return stack.pop().intValue(); //返回运算结果
}
public static void main(String args[]){
String expstr="121+10*(53-49+20)/((35-25)2+10)+11";
String postfix = toPostfix(expstr);
System.out.println("expstr= " + expstr);
System.out.println("postfix= " + postfix);
System.out.println("value= " + value(postfix));
}
}
/
程序运行结果如下：
expstr= 121+10*(53-49+20)/((35-25)*2+10)+11
postfix= 121 10 53 49 -20 +*35 25 -2 *10 +/+11 +
value= 140
expstr= 121+10*(53-49+20)/((35-25)*2+10)+11/0
postfix= 121 10 53 49 -20 +*35 25 -2 *10 +/+11 0 /+
Exception in thread “main” java.lang.ArithmeticException: / by zero
at Expression.value(Expression.java:79)
at Expression.main(Expression.java:93)
*/