目录

前缀、中缀、后缀表达式

概念

中缀表达式

中缀表达式是一种通用的算术或逻辑公式表示方法,操作符以中缀形式处于操作数中间。

前缀表达式(波兰表达式)

前缀表达式是一种没有括号的算术表达式,与中缀表达式不同的是,其运算符写在前面,操作数写在后面。例如1-(2+3)转成前缀表达式是- 1 + 2 3

后缀表达式

后缀表达式也没有括号,运算符放在两个运算对象的后面,所有的计算按运算符出现的顺序严格从左向右进行(不再考虑运算符的优先级)


虽然人的大脑很容易理解与分析中缀表达式,但对计算机来说中缀表达式却是很复杂的,因此计算表达式的值时,通常需要先将中缀表达式转换为前缀或后缀表达式,然后再进行求值。对计算机来说,计算前缀或后缀表达式的值非常简单。

快速转换

给出一个中缀表达式

1
a + b*c - (d+e)
  1. 按照运算符的优先级给所有的运算单位加上括号
1
((a+(b*c))-(d+e))
  1. 转换 2.1. 转前缀 运算符号移动到对应括号前面再去掉括号
1
2
    -( +(a * (b  c)) + (d e))
    -  + a * b c + d e
2.2. 转后缀
    运算符号移动到对应括号后面再去掉括号
1
2
    ((a (b c) *) + (d e) +)-
    a b c * + d e + -

前缀表达式

前缀表达式求值

从右至左扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(栈顶元素 op 次顶元素),并将结果入栈;重复上述过程直到表达式最左端,最后运算得出的值即为表达式的结果。

中缀表达式转换为前缀表达式

https://gitee.com/lienhui68/picStore/raw/master/null/20200618132052.png

后缀表达式

后缀表达式求值

与前缀表达式类似,只是顺序是从左至右: 从左至右扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(次顶元素 op 栈顶元素),并将结果入栈;重复上述过程直到表达式最右端,最后运算得出的值即为表达式的结果。

中缀表达式转换为后缀表达式

https://gitee.com/lienhui68/picStore/raw/master/null/20200618132118.png

使用后缀表达式实现一个计算器

要求

  1. 支持+ - * / ()
  2. 支持多位数和小数
  3. 兼容处理,过滤空白字符
  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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
package com.eh.ftd.dsa.ds.impl;

import com.eh.ftd.dsa.ds.Stack;
import com.google.common.collect.Lists;

import java.util.List;

/**
 * 后缀表达式(逆波兰表达式)
 *
 * @author David Li
 * @create 2020/06/18 10:20
 */
public class PostfixCalculator {

    enum SEG_KIND {
        LEFT_BRACKET, // 左括号
        RIGHT_BRACKET, // 右括号
        NUMBER, // 数字
        OPERATOR; // 运算符

        static SEG_KIND of(String s) {
            if ("(".equals(s)) {
                return LEFT_BRACKET;
            } else if (")".equals(s)) {
                return RIGHT_BRACKET;
            } else if (operators.contains(s.charAt(0))) {
                return OPERATOR;
            } else if (s.matches("^[-\\+]?(\\d+|\\d+\\.\\d+)$")) {
                return NUMBER;
            }
            throw new RuntimeException("转换seg种类出错!");
        }
    }

    /**
     * 操作符集合
     */
    private static final List<Character> operators = Lists.newArrayList('+', '-', '*', '/');

    /**
     * 操作符类
     */
    class Operator implements Comparable<Operator> {
        private char operator;
        private int priority;

        public Operator(char operator) {
            switch (operator) {
                case '+':
                case '-':
                    this.operator = operator;
                    this.priority = 0;
                    break;
                case '*':
                case '/':
                    this.operator = operator;
                    this.priority = 1;
                    break;
            }
        }

        @Override
        public int compareTo(Operator o) {
            return this.priority - o.priority;
        }

        public char getOperator() {
            return operator;
        }

    }


    /**
     * 计算表达式
     *
     * @param expression
     * @return
     */
    public Double calculate(String expression) {
        expression = expression.replace(" ", "");
        // 定义运算符栈s1和储存中间结果栈s2
        Stack<String> s1 = new ArrayStack<>(50);
        Stack<String> s2 = new ArrayStack<>(50);
        // 扫描表达式
        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);
            // 组装seg, 如果是数字需要特殊处理,考虑多位数以及小数点
            String seg = "";
            if (Lists.newArrayList(SEG_KIND.LEFT_BRACKET, SEG_KIND.RIGHT_BRACKET, SEG_KIND.OPERATOR).contains(SEG_KIND.of(String.valueOf(expression.charAt(i))))) {
                seg = String.valueOf(c);
            } else if (String.valueOf(c).matches("\\d|.")) {
                for (int j = i; j < expression.length(); j++) {
                    seg += expression.charAt(j);
                    // j是表达式最后一位或者当前字符下一位是符号(运算符号或者括号)则将该字符组装
                    if (j == expression.length() - 1 || (j < expression.length() - 1 && !String.valueOf(expression.charAt(j + 1)).matches("\\d|\\."))) {
                        i = j;
                        break;
                    }
                }
            }

            switch (SEG_KIND.of(seg)) {
                case NUMBER:
                    // 操作数直接压入s2
                    s2.push(seg);
                    break;
                case LEFT_BRACKET:
                    // 左括号直接压入s1
                    s1.push(seg);
                    break;
                case OPERATOR:
                    Operator cur = new Operator(seg.charAt(0));
                    Operator topOper = s1.isEmpty() ? null : new Operator(s1.peek().charAt(0));
                    // 如果运算符栈为空或者运算符栈顶元素是左括号或者运算符优先级大于s1栈顶运算符则直接压入s1
                    if (s1.isEmpty() || SEG_KIND.LEFT_BRACKET.equals(SEG_KIND.of(s1.peek())) || cur.compareTo(topOper) > 0) {
                        s1.push(seg);
                        break;
                    }
                    while (true) {
                        // 将s1栈顶运算符弹出并push到s2知道s1为空或者遇到左括号
                        s2.push(s1.pop());
                        if (s1.isEmpty() || SEG_KIND.LEFT_BRACKET.equals(SEG_KIND.of(s1.peek())) || cur.compareTo(topOper) > 0) {
                            break;
                        }
                    }
                    s1.push(seg);
                    break;
                case RIGHT_BRACKET:
                    // 弹出s1栈顶元素,如果是右括号则将这对括号丢弃否则压入s2
                    while (true) {
                        String str = s1.pop();
                        if ("(".equals(str)) {
                            break;
                        } else {
                            s2.push(str);
                        }
                    }
            }
        }
        // 将s1剩余的运算符依次弹出并压入s2,依次弹出s2的元素并输出,结果的逆序就是后缀表达式
        while (!s1.isEmpty()) {
            s2.push(s1.pop());
        }

        String[] data = new String[s2.size()];
        for (int i = data.length - 1; i >= 0; i--) {
            data[i] = s2.pop();
        }
        // 从左至右扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(次顶元素 op 栈顶元素),
        // 并将结果入栈;重复上述过程直到表达式最右端,最后运算得出的值即为表达式的结果。
        Stack<Double> numStack = new ArrayStack<>(50);
        for (int i = 0; i < data.length; i++) {
            if (SEG_KIND.NUMBER.equals(SEG_KIND.of(data[i]))) {
                numStack.push(Double.parseDouble(data[i]));
            } else if (SEG_KIND.OPERATOR.equals(SEG_KIND.of(data[i]))) {
                double num1 = numStack.pop();
                double num2 = numStack.pop();
                numStack.push(calculate(num1, num2, new Operator(data[i].charAt(0))));
            } else {
                throw new RuntimeException();
            }
        }
        return numStack.peek();
    }

    /**
     * 判断是否是操作符
     *
     * @param c
     * @return
     */
    private boolean isOperator(char c) {
        if (operators.contains(c)) {
            return true;
        }
        return false;
    }


    /**
     * 对两个数进行计算
     *
     * @param num1
     * @param num2
     * @param operator
     * @return num2 op num1
     */
    private double calculate(double num1, double num2, Operator operator) {
        switch (operator.getOperator()) {
            case '+':
                return num1 + num2;
            case '-':
                return num2 - num1;
            case '*':
                return num1 * num2;
            case '/':
                if (num1 == 0) {
                    throw new RuntimeException("被除数不能为0");
                }
                return num2 / num1;
        }
        throw new RuntimeException("操作非法");
    }

    public static void main(String[] args) {
        PostfixCalculator calculator = new PostfixCalculator();
        System.out.println(calculator.calculate("9.9+(3.2-1)*3+9.6/2"));
    }

}

运行结果 https://gitee.com/lienhui68/picStore/raw/master/null/20200618132212.png

简单表达式使用逆波兰计算

  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
118
119
120
121
122
123
124
125
package test;

import java.util.*;

public class Solution {

    static Map<String, Integer> priorityMap = new HashMap<>();

    static {
        priorityMap.put("+", 0);
        priorityMap.put("-", 0);
        priorityMap.put("*", 1);
        priorityMap.put("/", 1);
        priorityMap.put("#", -1);  // 方便统一操作
    }


    /**
     * 逆波兰表达式求值
     * <p>
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 返回表达式的值
     *
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    public int solve(String s) {
        return calculate(postExp(s));
    }

    // 中缀表达式转后缀表达式

    /**
     * 声明操作符栈,后缀表达式队列
     * 从左到右扫描字符串,如果是数值则直接入队
     * 左括号,入操作符栈
     * 右括号,操作符栈依次出栈并入队,直到遇到左括号,左括号舍弃
     * 操作数,如果优先级大于操作符栈顶元素优先级则入栈,否则操作符栈依次出栈并入队直到当前优先级大于栈顶元素优先级
     * 如果扫描到串尾,将操作数栈中剩余元素全部入队
     */
    private Queue<String> postExp(String s) {
        Queue<String> res = new LinkedList<>();
        Stack<String> opers = new Stack<>();
        opers.push("#");
        int start = 0; // 截取元素开始下标
        // 解析字符串
        List<String> resolve = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            if (priorityMap.keySet().contains(String.valueOf(s.charAt(i))) || '(' == s.charAt(i) || ')' == s.charAt(i)) { // 如果遇到操作符号
                if (!"".equals(s.substring(start, i))) { // 过滤类似"+("、")*" 类似情况
                    resolve.add(s.substring(start, i));
                }
                resolve.add(String.valueOf(s.charAt(i)));
                start = i + 1;
            } else if (i == s.length() - 1) { // 如果遍历到串尾
                resolve.add(s.substring(start));
            }
        }

        for (int i = 0; i < resolve.size(); i++) {
            String element = resolve.get(i);
            if (priorityMap.keySet().contains(element)) { // 操作数
                // 入队
                while (!"(".equals(opers.peek()) && priorityMap.get(element) <= priorityMap.get(opers.peek())) {
                    res.offer(opers.pop());
                }
                // 入栈
                opers.push(element);
            } else if ("(".equals(element)) { // 左括号
                opers.push(element);
            } else if (")".equals(element)) { // 右括号
                while (!"(".equals(opers.peek())) {
                    res.offer(opers.pop());
                }
                // 忽略左括号,直接pop
                opers.pop();
            } else { // 数值
                res.offer(element);
            }
        }
        // 将操作数栈剩余元素入队后缀表达式
        while (!"#".equals(opers.peek())) {
            res.offer(opers.pop());
        }
        return res;
    }

    // 后缀表达式计算
    // 声明操作数栈
    // 遍历后缀表达式队列,如果是数值则入操作数栈,否则从操作数栈中依次出栈两个数,第一个是b,第二个是a,将运算结果a # b 入操作数栈
    private int calculate(Queue<String> postExp) {
        Stack<Integer> nums = new Stack<>();
        while (!postExp.isEmpty()) {
            String element = postExp.poll();
            if (priorityMap.keySet().contains(element)) { // 如果是操作符
                int b = nums.pop();
                int a = nums.pop();
                switch (element) {
                    case "+":
                        nums.push(a + b);
                        break;
                    case "-":
                        nums.push(a - b);
                        break;
                    case "*":
                        nums.push(a * b);
                        break;
                    case "/":
                        nums.push(a / b);
                        break;
                }
            } else { // 如果是操作数
                nums.push(Integer.parseInt(element));
            }
        }
        return nums.pop();
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        // 6 4 3 + 6  * 2  / + 7 -
        System.out.println(solution.solve("((10+2)*10-(100-(10+20*10-(2*3)))*10*1*2)-2"));
    }

}

参考资料

(数据结构)前缀,后缀以及中缀表达式: https://blog.csdn.net/weixin_39241397/java/article/details/79933009 数据结构-前缀、中缀、后缀表达式: https://blog.csdn.net/qq248/article/details/52043952