逆波兰式的实现以及计算_逆波兰式计算的过程

逆波兰式的实现以及计算

什么是逆波兰表达式

逆波兰表达式又叫做后缀表达式。逆波兰表示法是波兰逻辑学家J・卢卡西维兹(J・ Lukasiewicz)于1929年首先提出的一种表达式的表示方法 。在计算机中，对于后缀表达式的计算是容易的，对中缀表达式的计算的是非常不易的。

将中缀表达式转换成逆波兰表达式

在我们人类世界中，对中缀表达式是十分明确，可读性十分高，但是对于计算机不然，所以在我们的计算机计算表达式中，都是通过转化成后缀表达式，也就是逆波兰表达式计算。那么是怎么样子去转换的呢？
在数据结构中，我们有一个stack数据结构，能够帮助我们完成表达式的转换和计算 。

思路分析

将中缀表达式转化成逆波兰表达式有这么8个步骤：

例如：1+（（2+3）*4）-5

代码实现

首先我们观察 s2 栈中只关心放入元素，没有取出元素，而且后续要得要逆波兰表达式还需要将s2 栈进行逆序输出这显然很麻烦 ，所以我们干脆 对于s2 而言 不使用栈这种数据结构，而使用 数组这种线性结构，这样放入的顺序 与取出的顺序 一致 不需要进行逆序这一步操作。
为了操作方便，我先将中缀表达式的字符串 转化成一个List 方便遍历扫描 。
主要代码

/**
   * 将一个中缀字符串转化为一个中缀集合List
   *
   * @param s
   * @return
   */
  public static List<String> toInfixExpressList(String s) {

    int index = 0;
    String str = ""; // 用来拼接的
    char c;
    List<String> list = new ArrayList<>();
    do {
      if ((c = s.charAt(index)) < 48 || (c = s.charAt(index)) > 57) {
        // 说明是字符
        list.add("" + c);
        index++;
      } else {
        // 判断多位数
        while (index < s.length() && (c = s.charAt(index)) >= 48 && (c = s.charAt(index)) <= 57) {
          str += c;
          index++;
        }
        list.add(str);
        str = "";
      }
    } while (index < s.length());
    return list;
  }

  /**
   * 将中缀表达式的list 转化成 后缀表达式的String
   *
   * @param insuffix
   * @return
   */
  public static List<String> parseSuffixList(List<String> insuffix) {

    // 运算符栈
    Stack<String> oper = new Stack<>();
    // 存放中间结果
    List<String> mid = new ArrayList<>();
    for (String s : insuffix) {

      // 如果是数值
      if (s.matches("\\d+")) {
        mid.add(s);
      } else if (oper.isEmpty() || "(".equals(oper.peek())) {
        oper.push(s);
      } else if (")".equals(s)) {
        // 消除括号
        while (!oper.isEmpty() && !"(".equals(oper.peek())) {
          // 弹出的直接加入list
          mid.add(oper.pop());
        }
        // 将小括号弹出去 (
        oper.pop();
      } else {
        // 比较优先级 该优先级小于栈顶优先级
        if (priority(s) <= priority(oper.peek())) {
          // 比栈顶优先级低 说明该运算符在栈顶元素下面 ，将栈顶元素弹出放入mid中
          mid.add(oper.pop());
          // 该运算符 加入到oper栈
        }
          oper.push(s);
        }
      }
    // 此时扫描完成了，然后将oper中元素全部加入 mid中
    while (!oper.isEmpty()) {
      mid.add(oper.pop());
    }
    return mid;
  }
  // 定义优先级
  public static int priority(String s) {

    switch (s) {
      case "*":
      case "/":
        return 2;
      case "-":
      case "+":
        return 1;
      default:
        throw new RuntimeException("该符号不存在");
    }
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

计算逆波兰表达式

刚才上一步我们求得了逆波兰表达式 ，那么计算机怎么计算这个逆波兰表达式的呢？

思路分析

由于对于计算机而言，对逆波兰表达式的计算是十分简单的，这主要思路是这样的：

需要一个栈stack结构帮我们存放操作数 与中间运算结果

1. 逐个扫描后缀表达式 ，如果是一个操作符，那么从stack中弹出两个操作数，进行计算 ，然后将运算结果压栈
2. 如果是一个操作数的话，那么直接压栈即可。
3. 扫描结束后，栈中的元素就是计算该表达式的计算结果。

代码实现

/**
   * 计算后缀表达式
   * @param list
   * @return
   */
  public static int calculate(List<String> list) {

    int res = 0;
    Stack<String> stack = new Stack<>();
    for (String s : list) {
      // 如果是数值 ,使用正则去匹配呢，jdk8中能够使用正则表达式进行匹配

      if (s.matches("\\d+")) {
        stack.push(s);
      } else {
        // 是操作符 那么就要计算了
        int num2 = Integer.parseInt(stack.pop());
        int num1 = Integer.parseInt(stack.pop());
        switch (s) {
          case "+":
            res = num1 + num2;
            break;
          case "-":
            res = num1 - num2;
            break;
          case "*":
            res = num1 * num2;
            break;
          case "/":
            res = num1 / num2;
            break;
        }
        stack.push("" + res);
      }
    }

    return Integer.parseInt(stack.pop());
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

代码测试

测试代码

 public static void main(String[] args) {

    // 中缀表达式转后缀表达式
    String inffix="4*5-8+60+8/2";
    List<String> infixExpressList = toInfixExpressList(inffix);
    System.out.println(infixExpressList);
    List<String> strings = parseSuffixList(infixExpressList);
    System.out.println(strings);
    int calculate = calculate(strings);
    System.out.println(calculate);
    // 这里为了方便我们每个数值与符号之间空个空格
   // String suffixExpression = "4 5 * 8 - 60 + 8 2 / +";
    // 放入list 通过list 遍历后缀表达式
//    List<String> list = getListByExpression(suffixExpression);
//    int calculate = calculate(list);
//    System.out.println(calculate);
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

测试结果