本文共 3623 字,大约阅读时间需要 12 分钟。
栈是嵌套调用机制的实现基础
使用栈以非递归方式实现递归算法
package pers.zhang.stack;/** * @author zhang * @date 2020/1/16 - 14:42 * * 栈应用:括号匹配 */public class Exp_bracket { //判断expstr表达式中的圆括号是否匹配,若匹配,返回空串,否则返回错误信息 public static String isValid(String expstr){ SeqStackstack = new SeqStack (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))( 期望(*/
/**
@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= 140expstr= 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)*/
转载地址:http://bypqb.baihongyu.com/