算符优先分析求中缀表达式

发表于 更新于 分类于 ， 阅读次数： 本文字数： 763 阅读时长 ≈ 3 分钟

算符优先分析法：它只考虑算符（终结符）之间的优先关系，分析扫描每个规约式的算符间优先关系。本文将使用算符优先分析法实现求中缀表达式的值。

算符优先分析求中缀表达式

定义一个表达式的二义性文法

\[ E\rightarrow E+E \, | \, E-E \, | \, E*E \, | \, E/E \, | \, (E) \, | \, i \]

定义运算规则

对以上表达式的文法按公认的计算顺序规定优先级和结合性如下：

  • 对于运算对象的终结符 \(i\) ，其优先级最高

  • \(*，/\) 优先级其次，服从左结合。相当于 \(*>*、*>/、/>/、/>*\)
  • \(+，-\) 优先级最低，服从左结合。相当于 \(+>+、+>-、->-、->+\)
  • 对于 \(“(”，“)”\) 规定括号的优先性大于括号外的运算符，小于括号内的运算符，内括号的优先性大于外括号。

  • 对于句子括号 "#" 规定与它相邻的任何运算符的优先性都比它大。

算符优先关系表

根据定义的优先规则可以构造出如下优先关系表：

+ - * / ( ) i #
+ > > < < < > < >
- > > < < < > < >
* > > > > < > < >
/ > > > > < > < >
( < < < < < = <
) > > > > > >
i > > > > > >
# < < < < < < =

所给表达式文法虽然是二义性的，但我们人为直观地给出运算符之间的优先关系且这种优先关系是唯一的，有了这个优先关系表我们对与符合文法的表达式的归约过程就是唯一确定的了。

算符优先归约过程

以分析输入串 \(i_1+i_2*i_3\) 为例：

步骤 栈 优先关系 当前符号 剩余输入串 移进或归约
(1) # < \(i_1\) +\(i_2\)*\(i_3\)# 移进
(2) #\(i_1\) > + \(i_2\)*\(i_3\)# 归约\(E \rightarrow i\)
(3) #E < + \(i_2\)*\(i_3\)# 移进
(4) #E+ < \(i_2\) *\(i_3\)# 移进
(5) #E+\(i_2\) > * \(i_3\)# 归约\(E \rightarrow i\)
(6) #E+E < * \(i_3\)# 移进
(7) #E+E* < \(i_3\) # 移进
(8) #E+E*\(i_3\) > # 归约\(E \rightarrow i\)
(9) #E+E*E > # 归约\(E \rightarrow E*E\)
(10) #E+E > # 归约\(E \rightarrow E+E\)
(11) #E = # 接受

计算中缀表达式的值

创建两个辅助栈 stackOper 和 stackData ，扫描中缀表达式时，用 stackOper 存储表达式中的运算符，用 stackData 存储操作数。

stackOper 栈顶运算符对应着算符优先关系表第一纵列的运算符，每次从表达式中扫描到的运算符对应着算符优先关系表第一横行的运算符。

基本思想：

  1. 首先置 stackOper 和 stackData 为空栈

  2. 向 stackOper 压入运算符 # ，在表达式后面加上 # (作为结束标志)

  3. 依次扫描表达式中的每一个字符，若是操作数，则将操作数压入 stackData 中；

  • 若是运算符，则将运算符和 stackOper 栈顶的运算符比较优先级后做相应操作 (若栈顶运算符优先级高，则 stackData 连续弹出两个数， stackOper 弹出运算符，按弹出的运算符计算出结果后，将结果压入 stackData ；否则，直接将新扫描的运算符压入 stackOper )；
  • 否则，表达式文法错误，抛异常
  1. 直至整个表达式扫描完毕， stackData 栈顶的数值就是运算结果
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
import java.util.LinkedList;

/**
 * @author wylu
 * @version 1.0
 * 利用算符优先文法求中缀表达式的值
 */
public class Calculator {

    private static final String EXPRESSION_END_FLAG = "#";
    private static final String WRONG_EXPRESSION = "文法错误";

    private static final char ZERO = '0';
    private static final char NINE = '9';

    /**
     * 栈顶运算符比前扫描到的运算符优先级高
     */
    private static final int PRIORITY_HIGH = 1;
    /**
     * 栈顶运算符与前扫描到的运算符优先级相等
     */
    private static final int PRIORITY_EQUAL = 0;
    /**
     * 栈顶运算符比前扫描到的运算符优先级低
     */
    private static final int PRIORITY_LOW = -1;
    /**
     * 非法运算符
     */
    private static final int OPERATOR_DEDY = 2;


    /**
     * 1）先乘除，后加减
     * 2）同级运算，从左到右依次计算
     * 3）有括号的，先算括号里面的
     *
     * 根据以上三条规则定义如下算符优先关系表：
     *     > : 行位置的运算比列位置的运算的优先级高
     *     < : 行位置的运算比列位置的运算的优先级低
     *     = : 行位置的运算与列位置的运算的优先级相等
     *     $ : 表示这两种运算之间没有可比性，说明输入的式子有文法错误
     */
    private static final String[][] PRIORITY_TABLE = {
            {"$", "+", "-", "*", "/", "(", ")", "#"},
            {"+", ">", ">", "<", "<", "<", ">", ">"},
            {"-", ">", ">", "<", "<", "<", ">", ">"},
            {"*", ">", ">", ">", ">", "<", ">", ">"},
            {"/", ">", ">", ">", ">", "<", ">", ">"},
            {"(", "<", "<", "<", "<", "<", "=", "$"},
            {")", ">", ">", ">", ">", "$", ">", ">"},
            {"#", "<", "<", "<", "<", "<", "$", "="},
    };


    /**
     * 创建两个辅助栈stackOper和stackData，
     * 扫描中缀表达式时，用stackOper存储表达式中的运算符，用stackData存储操作数。
     * stackOper栈顶运算符对应着算符优先关系表第一纵列的运算符，
     * 每次从表达式中扫描到的运算符对应着算符优先关系表第一横行的运算符。
     * 求中缀表达式的基本思想如下：
     * 1) 首先置stackOper和stackData为空栈
     * 2) 向stackOper压入运算符#，在表达式后面加上#(作为结束标志)
     * 3) 依次扫描表达式中的每一个字符，若是操作数，则将操作数压入stackData中；
     *    若是运算符，则将运算符和stackOper栈顶的运算符比较优先级后做相应操作
     *    (若栈顶运算符优先级高，则stackData连续弹出两个数，stackOper弹出运算符，
     *    按弹出的运算符计算出结果后，将结果压入stackData;
     *    否则，直接将新扫描的运算符压入stackOper)；
     *    否则，表达式文法错误，抛异常
     * 4) 直至整个表达式扫描完毕，stackData栈顶的数值就是运算结果
     * @param expression 中缀表达式
     * @return 计算结果的字符串形式
     */
    public static String cal(String expression) {

        String express = expression.replaceAll("\\s*", "") + EXPRESSION_END_FLAG;

        LinkedList<String> stackOper = new LinkedList<>();
        LinkedList<Double> stackData = new LinkedList<>();

        stackOper.push(EXPRESSION_END_FLAG);

        char ch;

        for (int i = 0; i < express.length();) {
            ch = express.charAt(i);
            //操作数
            if (ch >= ZERO && ch <= NINE) {
                if (i == express.length() - 2) {
                    stackData.push((double) (ch - ZERO));
                    i++;
                } else {
                    int j = i + 1;
                    while (express.charAt(j) >= ZERO
                           && express.charAt(j) <= NINE) j++;
                    stackData.push(Double.valueOf(express.substring(i, j)));
                    i = j;
                }
            } else { //运算符
                switch (judgePriority(stackOper.peek(), ch)) {
                    case PRIORITY_HIGH:
                        stackData.push(operate(stackData.pop(), stackData.pop(), stackOper.pop()));
                        break;
                    case PRIORITY_EQUAL:
                        stackOper.pop();
                        i++;
                        break;
                    case PRIORITY_LOW:
                        stackOper.push(ch + "");
                        i++;
                        break;
                    default:
                        throw new RuntimeException(new Exception(WRONG_EXPRESSION));
                }
            }
        }

        if (!stackOper.isEmpty()) throw new RuntimeException(new Exception(WRONG_EXPRESSION));

        return String.valueOf(stackData.pop());
    }

    private static Double operate(Double num1, Double num2, String operator) {
        switch (operator) {
            case "+":
                return num2 + num1;
            case "-":
                return num2 - num1;
            case "*":
                return num2 * num1;
            case "/":
                return num2 / num1;
            default:
                return 0.0;
        }
    }

    private static int judgePriority(String stackTopOper, char currentOper) {
        return judgePriority(stackTopOper, currentOper + "");
    }

    /**
     * 比较栈顶运算符和当前扫描的运算符的优先级高级
     * @param stackTopOper 栈顶运算符
     * @param currentOper 当前扫描到的运算符
     * @return 魔数 PRIORITY_HIGH=1 PRIORITY_EQUAL=0 PRIORITY_LOW=-1
     */
    private static int judgePriority(String stackTopOper, String currentOper) {
        if (stackTopOper == null || currentOper == null) return OPERATOR_DEDY;

        int row = 1, col = 1;
        while (row < PRIORITY_TABLE.length
                && !PRIORITY_TABLE[row][0].equals(stackTopOper)) row++;
        while (col < PRIORITY_TABLE[0].length
                && !PRIORITY_TABLE[0][col].equals(currentOper)) col++;

        if (row == PRIORITY_TABLE.length || col == PRIORITY_TABLE[0].length) {
            return OPERATOR_DEDY;
        }

        switch (PRIORITY_TABLE[row][col]) {
            case ">":
                return PRIORITY_HIGH;
            case "<":
                return PRIORITY_LOW;
            case "=":
                return PRIORITY_EQUAL;
            default:
                return OPERATOR_DEDY;
        }
    }

    public static void main(String[] args) {
//        String expression = "2*(3-1)+(5+4)/9";
        String expression = "(5+4)/9+11";
        System.out.println(Calculator.cal(expression));
    }
}