中缀表达式转后缀表达式

一、中缀表达式和后缀表达式的区别：

• 中缀表达式就是我们通常认知中的表达式，比如1+((2+3)*4)-5，这样的表达式虽然容易被人所理解，但是不容易被机器所识别，为此推出了后缀表达式。
• 后缀表达式又被叫做逆波兰表达式，逆波兰表达式不需要被括号所识别，且容易被机器识别。

二、中缀表达式转后缀表达式的过程：

我们随意的拟定一个中缀表达式，比如：1+5*(3+2)-4*5；
我们对中缀表达式进行一步一步转换，转换方式如下：
1、遇到操作数时直接加入集合
2、遇到操作符，与栈顶操作符比较优先级
  2.1、如果栈为空，或者栈顶元素为’(’，直接加入栈。
  2.2、如果优先级比栈顶操作数高，直接加入栈。
  2.3、如果优先级比栈顶操作符低或者相等，则弹出栈顶元素入集合，再次进行对比
3、遇到括号时：
  3.1、如果为左括号，直接加入栈
  3.2、如果为右括号，依次弹出栈顶元素入集合，并且再次对比，直到遇到左括号，弹出栈顶元素不入集合。
4、最后将栈顶元素依次弹出入集合。
做从左向右扫描，转化过程如下：

三、代码实现过程：
根据上述的转换方式编写代码，首先我们需要一个对运算符的优先级判定的方式，我采取的是枚举类的方式进行判断，后期可以根据自己的需要去添加。

package algorithm.PostfixExpression;

public enum Operator {
    ADD("+",1),
    REDUCE("-",1),
    RIDE("*",2),
    EXCEPT("/",2);

    int value;
    String operator;

    private Operator(String operator,int value) {
        this.operator=operator;
        this.value=value;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

package algorithm.PostfixExpression;


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

/**
 * 中缀表达式转为后缀表达式：
 * 1、创建一个栈和一个List集合，栈用于弹出弹入数据，集合用于存放结果
 * 2、首先将字符串转换为字符串数组
 */
public class PostfixExpression {
    public static void main(String[] args) {
        String str = "1+5*(3+2)-4*5";
        String[] strArray = new String[str.length()+1];
        System.out.println(strArray.length);
        //把字符串数组设置为空而非null
        for (int i = 0;i < strArray.length; i++){
            strArray[i] = "";
        }
        int k = 0;
        for (int i = 0; i < str.length(); i++){
            if (Character.isDigit(str.charAt(i))){
                strArray[k]+=str.charAt(i);
            }else {
                if (!Character.isDigit(str.charAt(i-1))){
                    strArray[k]+=str.charAt(i);
                    k++;
                }else {
                    k++;
                    strArray[k]+=str.charAt(i);
                    k++;
                }

            }
        }
        Arrays.stream(strArray).forEach(s -> {
            System.out.println(s);
        });

        System.out.println("--------------------------------");
        PostfixExpression postfixExpression = new PostfixExpression();
        postfixExpression.inToPostExpression(strArray);
    }

    /*
    中缀表达式转化为后缀表达式
    1、遇到操作数时直接加入集合
    2、遇到操作符，与栈顶操作符比较优先级
        2.1、如果栈为空，或者栈顶元素为'('，直接加入栈。
        2.2、如果优先级比栈顶操作数高，直接加入栈。
        2.3、如果优先级比栈顶操作符低或者相等，则弹出栈顶元素入集合，再次进行对比
    3、遇到括号时：
        3.1、如果为左括号，直接加入栈
        3.2、如果为右括号，依次弹出栈顶元素入集合，并且再次对比，直到遇到左括号，弹出栈顶元素不入集合。
    4、最后将栈顶元素依次弹出入集合。
     */

    public void inToPostExpression(String[] str){
        Stack<String> stack = new Stack<>();
        List<String> list = new ArrayList<>();
        int i = 0;
        while (str[i] != ""){
            //遇到操作数时直接加入集合
            if (str[i].matches("\\d+")){
                list.add(str[i]);
                //遇到括号时的情况
            }else if ("(".equals(str[i])){
                stack.push(str[i]);
            }else if (")".equals(str[i])){
                while (!"(".equals(stack.peek())){
                    list.add(stack.pop());
                }
                stack.pop();
                //遇到操作符，与栈顶操作符比较优先级
            }else {
                //如果优先级比栈顶操作符低或者相等，则弹出栈顶元素入集合，再次进行对比
                while (stack.size() != 0 && !judgeOperator(str[i], stack.peek())){
                    list.add(stack.pop());
                }
                stack.push(str[i]);
            }
            i++;
        }
        for (int j = 0;j < stack.size();i++){
            list.add(stack.pop());
        }

        list.forEach(s -> {
            System.out.print(s+' ');
        });
    }

    //对比两个运算符的优先级
    public boolean judgeOperator(String a, String b){
        int value1 = 0;
        int value2 = 0;
        for (Operator item : Operator.values()){
            if (item.operator.equals(a)){
                value1 = item.value;
            }
        }
        for (Operator item : Operator.values()){
            if (item.operator.equals(b)){
                value2 = item.value;
            }
        }

        if (value1 > value2){
            return true;
        }
        return false;
    }

}
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

其实并不难理解，只需要将过程理清楚，然后代码一点一点去编写就能够实现！我的实现方法肯定不是最优的，但是是我通过转换方式一条一条实现的。希望这篇文章有帮到你！