【Java数据结构】用栈实现后缀表达式求值

后缀表达式,即逆波兰式,是波兰逻辑学家卢卡西维奇(Lukasiewicz)发明的一种表示表达式的方法。这种表示方式把运算符写在运算对象的后面,例如,把a+b写成ab+,所以也称为后缀式。
——百度百科_后缀式

算法规则:

1、建立一个栈S

2、从左到右读表达式,如果读到操作数就将它压入栈中,如果读到运算符(一般是二元操作符,例如+、-、*、/)则取出由栈顶向下的前2个元素,按操作符规则运算

3、再将运算的结果代替原栈顶取出来的2个元素,压入栈S中 。如果后缀表达式未读完,则重复上面过程,最后输出栈顶的数值则为结束。

代码实现:

首先定义一个PostfixEvaluator类,定义好操作符常量,并在构造函数中初始化一个栈。


public class PostfixEvaluator {
 //定义操作符常量
 private final static char ADD = '+';
 private final static char SUBTRACT = '-';
 private final static char MULTIPLY = '*';
 private final static char DIVIDE = '/';
 //栈
 private Stack<Integer> stack;
 //构造函数初始化栈
 public PostfixEvaluator(){
 stack = new Stack<Integer>();
 }

接下来,取出栈顶的元素,做判断和计算


/**
 * 将表达式存入栈
 * @param expresion 表达式
 * @return 表达式的值
 */
 public int evaluate(String expresion) {
 // TODO Auto-generated method stub
 int op1,op2,result = 0;//临时变量,保存操作符和中间结果
 String token;//字符
 Scanner parser = new Scanner(expresion);
 //循环获取每一个字符
 while (parser.hasNext()) {
 token = parser.next();
 //如果是表达式,就弹出
 if(isOperator(token)){
 op2 = (stack.pop()).intValue();
 op1 = (stack.pop()).intValue();
 //计算中间结果
 result = evaluateSingleOperator(token.charAt(0),op1,op2);
 //将中间结果压入栈
 stack.push(new Integer(result));
 }else {
 //不是操作符就直接压入栈
 stack.push(new Integer(Integer.parseInt(token)));
 }
 }
 return result;
 }

中间计算用到了下面的方法,来计算每一个操作符左右两边的值


/**
 * 计算每一部分的表达式
 * @param operator 操作符
 * @param op1 中间变量,操作符左边
 * @param op2 中间变量,操作符左边
 * @return 中间结果
 */
 private int evaluateSingleOperator(char operator, int op1, int op2) {
 // TODO Auto-generated method stub
 int result = 0;
 //分情况计算
 switch (operator) {
 case ADD:
 result=op1+op2;
 break;
 case SUBTRACT:
 result=op1-op2;
 break;
 case MULTIPLY:
 result=op1*op2;
 break;
 case DIVIDE:
 result=op1/op2;
 break;
 }
 return result;
 }

判断字符是不是操作符,用到了下面的方法:


/**
 * 判断是否为操作符
 * @param token 字符
 * @return
 */
 private boolean isOperator(String token) {
 // TODO Auto-generated method stub
 return (token.equals("+")||token.equals("-")||token.equals("*")||token.equals("/"));
 }

这样主要的功能类就实现了,下面是测试类。

主要是获取用户的输入的表达式,然后从左到右去读表达式并且做相应的处理,并且为了能够连续计算,使用循环去获取每一次的表达式:


public class PostfixTester {

public static void main(String[] args) {
 // TODO Auto-generated method stub
 String expresion,again; //表达式
 int result; //结果

 Scanner in = new Scanner(System.in); //获取输入

 do{
 System.out.println("请输入一个后缀表达式,每一个字符用空格分开,\n每一个字符必须是一个整数或者一个运算符");
 PostfixEvaluator evaluator = new PostfixEvaluator();
 expresion = in.nextLine();//获取输入
 result = evaluator.evaluate(expresion);//计算
 System.out.println("\n这个表达式的值是:"+result);

 System.out.println("还要继续输入表达式么?[y/n]");
 again = in.nextLine();//重复获取表达式
 System.out.println();

 }
 while(again.equalsIgnoreCase("y"));
 }

}

这样就用栈实现了后缀表达式的求值。

参考资料:《Java软件结构与数据结构》

刘凯宁
20150314

Share