逆波兰计算器（Java实现）

之前的一篇博客中，讲的是用栈实现了中缀表达式的简易计算器，对于我们人来讲，中缀表达式是一种比较直观，而且非常好计算的一种形式，但对于计算器来讲，非常的难去看懂。所以，下面我讲下逆波兰计算器的Java实现。

逆波兰式（后缀表达式）

逆波兰表达式又叫做后缀表达式。逆波兰表示法是波兰逻辑学家J・卢卡西维兹(J・ Lukasewicz)于1929年首先提出的一种表达式的表示方法 [1]  。后来,人们就把用这种表示法写出的表达式称作“逆波兰表达式”。逆波兰表达式把运算量写在前面,把算符写在后面。

-------摘自百度

逆波兰式的转换方法

我主要讲解下前缀表达式如何转换成后缀表达式。举例：4*5-8+60+8/2

根据该表达式可以画出对应的二叉树，然后根据后序遍历（从下往上，从左到右再到根），遍历的结果是4 5 * 8 - 60 + 8 2 / +

所以得到的逆波兰表达式就是4 5 * 8 - 60 + 8 2 / +

分析：

前面的中缀表达式的实现，使用了两个栈，一个是数栈，一个是符号栈。在后缀表达式中，只需要使用一个栈就可以完成简易的计算。遍历表达式，如果出现数字，则直接将数字压入栈中。如果出现的是符号就直接将栈中弹出两个数进行计算，再将计算得到的值放入栈中，一直循环计算，最终放入栈中的值就是表达式的计算结果。

代码实现

package cn.mrlij.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 逆波兰表达式计算器实现
 */
public class PolandNotation {
 public static void main(String[] args) {
  //4*5-8+60+8/2
  String expression = "4 5 * 8 - 60 + 8 2 / +";
  List<String> list = getStrList(expression);
  System.out.println(list);
  //计算值，得结果
  int res = calc(list);
  System.out.println(res);
 }

 /**
  * 遍历表达式，并将遍历的结果放入list中
  * @param exp 表达式
  * @return
  */
 public static List<String> getStrList(String exp){
  String arr[] = exp.split(" ");//将字符串遍历得到数组
  List<String> list = new ArrayList<>();
  for(String str : arr){
   list.add(str);
  }
  return list;
 }
 //计算表达式
 public static int calc(List<String> list ){
  //创建存放字符串的栈
  Stack<String> stack = new Stack<>();
  //遍历list
  for (int i = 0;i<list.size();i++){
   //正则表达式匹配是否是数字
   if(list.get(i).matches("\\d+")){
    stack.push(list.get(i));//是数字则放入栈中
   }else {
    int num2 = Integer.parseInt(stack.pop());//弹出数字1
    int num1 = Integer.parseInt(stack.pop());//弹出数字2
    int res = 0;
    //进行运算
    if(list.get(i).equals("+")){
     res = num1 + num2;
    }else if(list.get(i).equals("-")){
     res = num1 - num2;
    }else if(list.get(i).equals("*")){
     res = num1 * num2;
    }else if(list.get(i).equals("/")){
     res = num1/num2;
    }else {
     throw new RuntimeException("不是操作符号！");
    }
    stack.push(""+res);
   }
  }
  //留在栈中的值就是最后的计算表达式结果
  return Integer.parseInt(stack.pop());
 }
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。