Please enable Javascript to view the contents

Matlab 解析表达式

 ·  ☕ 8 分钟  ·  👽 zhaoqiu

Matlab借助其强大的Gui控件可以很容易地开发可视化程序，让处理数据的过程更加交互化。对于解析Gui输入框中手动输入的表达式（比如：a + b / ln(c)，a，b可以代表运行时产生的变量的字符串名称，通过索引来映射：list = ['a','b']，data = [1 2])，程序需要实现堆栈类，通过根据优先级进行计算、出栈、入栈的操作。

解析表达式常用的算法有两种：

  1. 将表达式转换成后缀表达式，然后使用堆栈进行计算
  2. 直接进行堆栈，计算中间结果的同时考虑预算优先级

这里使用的是后缀表达式，这种方式较为优雅。首先，我们正常人类识别的计算公式为中缀表达式，例如：2+(-1+11)*ln(e^2)。中缀表达式中各个运算符的优先级只能人类识别，而后缀表达式运算优先级只有一个方向。2+(-1+11)*ln(e^2) 转换为后缀表达式为：'2 1 11 - e 2 ^ ln * + '，先来看后缀表达式如何计算：

定义两个堆栈：操作数堆栈、运算符堆栈。从左至右读取表达式，如果是操作数（数值），就入栈，如果是运算符，就根据不同运算符需要的操作数个数不同从操作数堆栈弹出，然后计算，将结果压入操作数堆栈，继续扫描表达式。

转化为后缀表达式的过程:

核心是操作符的优先级。定义一个运算符堆栈，从左至右扫描表达式，如果是操作数，就输出（拼接字符串，或者通过堆栈来接收)，如果是运算符，记op：

  1. 若为 (:
    直接入栈
  2. 若为 ):
    则不断将运算符堆栈弹出，直至 (
  3. 若为其他运算符：
    • 若堆栈为空，则直接入栈，否则
    • 若栈顶为(，则直接入栈
    • 比较op和栈顶运算符的优先级，如果op运算级高（不包括等于），将op入栈
    • 如果栈顶运算符优先级大于等于op，将栈顶运算符弹出，继续将op与此时栈顶运算符比较，直至堆栈为空，

对于2+(1-11)*ln(e^2)，具体过程如下：

  1. 第一个字符为2，输出2
  2. 读至+，此时栈为空，直接入栈
  3. 读至(，直接入栈
  4. 读至1，直接输出：2 1
  5. 读至-，此时栈顶运算符为(，直接入栈。
  6. 读至11，输出2 1 11
  7. 读至)，则不断弹出栈，直至(，输出：2 1 11 -，此时栈中有：+
  8. 读至*，此时栈顶运算符为+，优先级：* > +，直接入栈
  9. 读至ln，此时栈顶运算符为*，优先级：ln > *，直接入栈
  10. 读至(，直接入栈，此时栈中有：+ * ln (
  11. 读至e，直接输出：2 1 11 - e
  12. 读至^，此时栈顶运算符为(，直接入栈。此时栈中有：+ * ln ( ^
  13. 读至2，直接输出：2 1 11 - e 2
  14. 读至)，则不断弹出栈，直至(，输出：2 1 11 - e 2 ^，此时栈中有：+ * ln
  15. 表达式扫描结束，将堆栈剩余运算符依次弹出，输出：2 1 11 - e 2 ^ ln * +

示例

运行时解析表达式

字符串操作Tips：

  • 字符串比较：strcmp(s1,s2); 字符串分割：strsplit(s,delemiter);
  • 不可用==进行字符串比较，不可用split分割字符串
  • 查询时候包含某个字符串：ismember(strGroup, oneStr)，将字符串数组作为第一参数，方便获得索引。
  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
213
214
215

clear
expression = '2+(1-11)*ln(e^2)';
postfixExp = transformPostfixExpression(expression);
result = evalPostFixExpression(postfixExp);
function value = evalPostFixExpression(expression)
    resultStack = Stack;
    expression = strsplit(expression);
    for i=1:length(expression)
       switch expression{i}
           case {'--'}
               [resultStack,value] = resultStack.pop();
               value = - value;
               resultStack = resultStack.push(value);
           case {'ln'}
               [resultStack,value] = resultStack.pop();
               value = log(value);
               resultStack = resultStack.push(value);
           case {'lg'}
               [resultStack,value] = resultStack.pop();
               value = log10(value);
               resultStack = resultStack.push(value);
           case {'^'}
               [resultStack,latter] = resultStack.pop();
               [resultStack,former] = resultStack.pop();
               value = former ^ latter;
               resultStack = resultStack.push(value);
           case {'+'}
               [resultStack,latter] = resultStack.pop();
               [resultStack,former] = resultStack.pop();
               value = former + latter;
               resultStack = resultStack.push(value);
           case {'-'}
               [resultStack,latter] = resultStack.pop();
               [resultStack,former] = resultStack.pop();
               value = former - latter;
               resultStack = resultStack.push(value);
           case {'*'}
               [resultStack,latter] = resultStack.pop();
               [resultStack,former] = resultStack.pop();
               value = former * latter;
               resultStack = resultStack.push(value);
           case {'/'}
               [resultStack,latter] = resultStack.pop();
               [resultStack,former] = resultStack.pop();
               value = former / latter;
               resultStack = resultStack.push(value);
           case {'e'}
               resultStack = resultStack.push(exp(1));
           otherwise
               resultStack = resultStack.push(str2double(expression{i}));
       end
    end
end

function postfixExp = transformPostfixExpression(expression)

    %{
    去除空格
    %}
    expression = replace(expression,' ','');
    %{
    加空格, 以便遍历所有字符
    %}
    tempExp = '';
    for i=1:length(expression)
        if expression(i) == '+' || expression(i) == '-' || expression(i) == '*' || expression(i) == '/' || expression(i) == '(' || expression(i) == ')' || expression(i) == '^'
            tempExp = [tempExp,' ',expression(i),' '];
        else
            tempExp=[tempExp,expression(i)];
        end
    end
    expression = tempExp;
    %{
    去除首尾可能的空格
    %}
    expression = strtrim(expression);
    expression = strsplit(expression,' ');
    %{
    转换成后缀表达式
    %}
    opStack = Stack;
    postfixExp = '';
    for i=1:length(expression)
        switch expression{i}
           case {'e','E'}
               postfixExp = [postfixExp,'e '];
           case '('
               opStack = opStack.push('(');
           case ')'
               if opStack.stackismember('(')
                   [opStack, op] = opStack.pop();
                   while op ~= '('
                        postfixExp = [postfixExp,op,' '];
                        [opStack, op] = opStack.pop();
                   end
               else
                   break
               end
           case '-'
               %{
               区别负号和减号，只要'-'前面有数字即为减号，其他皆为负号。负号用'--'代替
               %}
               if i == 1
                   opStack = opStack.push('--');
               elseif strcmp(expression{i-1}, '+') || strcmp(expression{i-1}, '-') || strcmp(expression{i-1}, '*') || strcmp(expression{i-1}, '/') || strcmp(expression{i-1}, '(') || strcmp(expression{i-1}, '^')
                     %{
                     按负号处理，例如e^-1，1/-3
                     %}
                     opStack = opStack.push('--');
               else
                   while ~opStack.stackisempty()
                       if strcmp(opStack.getTop() ,'(')
                           opStack = opStack.push('-');
                           break
                       elseif strcmp(opStack.getTop() ,'--')|| strcmp(opStack.getTop(), '^')|| strcmp(opStack.getTop(), '*')|| strcmp(opStack.getTop(), '/')|| strcmp(opStack.getTop() ,'ln') || strcmp(opStack.getTop() ,'lg')|| strcmp(opStack.getTop(), '+') || strcmp(opStack.getTop(), '-')
                            [opStack, op] = opStack.pop();
                            postfixExp = [postfixExp,op,' '];
                       else
                           opStack = opStack.push('-');
                           break
                       end

                   end
                   if opStack.stackisempty()
                       opStack = opStack.push(expression{i});
                   end
               end

           case '+'
               %{
               忽略一些代表正号的情况，例如ln(+5), e^+5
               %}
               if i==1 || strcmp(expression{i-1}, '+') || strcmp(expression{i-1}, '-') || strcmp(expression{i-1}, '*') || strcmp(expression{i-1}, '/') || strcmp(expression{i-1}, '(') || strcmp(expression{i-1}, '^')
                   break
               else
                   while ~opStack.stackisempty()
                       if strcmp(opStack.getTop(), '(')
                           opStack = opStack.push('+');
                           break
                       elseif strcmp(opStack.getTop(), '--')|| strcmp(opStack.getTop(), '^')|| strcmp(opStack.getTop(), '*')|| strcmp(opStack.getTop(), '/')|| strcmp(opStack.getTop() ,'ln') || strcmp(opStack.getTop() ,'lg')|| strcmp(opStack.getTop(), '+') || strcmp(opStack.getTop(), '-')
                            [opStack, op] = opStack.pop();
                            postfixExp = [postfixExp,op,' '];
                       else
                           opStack = opStack.push('+');
                           break
                       end

                   end
                   if opStack.stackisempty()
                       opStack = opStack.push(expression{i});
                   end
               end
           case {'*','/'}
               while ~opStack.stackisempty()
                       if strcmp(opStack.getTop(), '(')
                           opStack = opStack.push(expression{i});
                           break
                       elseif strcmp(opStack.getTop(), '--')|| strcmp(opStack.getTop(), '^')|| strcmp(opStack.getTop(), '*')|| strcmp(opStack.getTop(), '/')|| strcmp(opStack.getTop() ,'ln') || strcmp(opStack.getTop() ,'lg')
                            [opStack, op] = opStack.pop();
                            postfixExp = [postfixExp,op,' '];
                       else
                           opStack = opStack.push(expression{i});
                           break
                       end

               end
               if opStack.stackisempty()
                    opStack = opStack.push(expression{i});
               end
            case {'ln','lg'}
                while ~opStack.stackisempty()
                       if strcmp(opStack.getTop(), '(')
                           opStack = opStack.push(expression{i});
                           break
                       elseif strcmp(opStack.getTop(), '--')|| strcmp(opStack.getTop() ,'ln') || strcmp(opStack.getTop() ,'lg')
                            [opStack, op] = opStack.pop();
                            postfixExp = [postfixExp,op,' '];
                       else
                           opStack = opStack.push(expression{i});
                           break
                       end

                end
                if opStack.stackisempty()
                    opStack = opStack.push(expression{i});
                end
            case {'^'}
                while ~opStack.stackisempty()
                       if strcmp(opStack.getTop(), '(')
                           opStack = opStack.push(expression{i});
                           break
                       elseif strcmp(opStack.getTop(), '--')|| strcmp(opStack.getTop() ,'ln') || strcmp(opStack.getTop() ,'lg') || strcmp(opStack.getTop(), '^')
                            [opStack, op] = opStack.pop();
                            postfixExp = [postfixExp,op,' '];
                       else
                           opStack = opStack.push(expression{i});
                           break
                       end

                end
                if opStack.stackisempty()
                    opStack = opStack.push(expression{i});
                end
            otherwise
                postfixExp = [postfixExp,expression{i},' '];
        end
    end
    %{
    将栈中剩余的运算符弹出
    %}
    while ~opStack.stackisempty()
        [opStack, op] = opStack.pop();
        postfixExp = [postfixExp,op,' '];
    end
end

为了配合网页语法高亮，注释采用%{ %}

 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

classdef Stack
   properties
       count = 0;
       top=1;
       stack=cell(1);
   end
   methods

       function displayU(this)
           celldisp(this.stack);
       end
       function x = getTop(this)
           if this.count > 0
               x = this.stack{this.count};
           else
               x = '';
           end
       end
       %{
       判断是否为空
       %}
       function is = stackisempty(this)
           if this.count == 0
               is = true;
           else
               is = false;
           end
       end
       %{
       将堆栈置空
       %}
       function this = empty(this)
           this.count = 0;
           this.top = 1;
           this.stack = cell(1);

       end
       %{
       出栈
       %}
       function [this,x] = pop(this)
           if isempty(this)
               x = {};
           else
               x = this.stack{this.count};
               this.stack(this.count) = [];
               this.count = this.count - 1;
           end
       end
       %{
       入栈
       %}
       function this = push(this,x)
           this.count = this.count + 1;
           this.stack{this.count} = x;
       end
       %{
       遍历
       %}
       function is = stackismember(this,str)
            if this.stackisempty()
              is = false;
            else
              for i=1:this.count
                 if this.stack{i} == str
                     is = true;
                     return
                 end
              end
            end
       end
   end
end


  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
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250

clear
close all
f = figure;
f.Units='Normalized';
f.Name='解析表达式';
f.NumberTitle='off';
inputpanel=uipanel(f,'Position',[0,0.5,1,0.5],'Title','输入表达式','fontsize',12);
resultpanel=uipanel(f,'Position',[0,0.,1,0.5],'Title','计算结果','fontsize',12);
expressionedit=uicontrol(inputpanel,'Units','Normalized','Position',[0.25 0.4 0.5 0.2],'Style','edit','String','','fontsize',12,'Callback',{@exp_Callback, resultpanel});
info = {'运行时变量:';'a = [1 2;3 4]';'b = [5 6;7 8]';'nameList = {''a'',''b''}';};
uicontrol(inputpanel,'Style','text','Units','Normalized','String',info,'fontsize',12,'Position',[0.25 0.6 0.5 0.3]);

function exp_Callback(src,event,resultpanel)

    expression = get(src,'String');
    if ~isempty(expression)
        postfixExp = transformPostfixExpression(expression);
        result = evalPostFixExpression(postfixExp);
        resulttable = uitable(resultpanel,'Data',result,'Units','Normalized','Position',[0 0 1 1],'ColumnName','','RowName','');
    end
end
function value = evalPostFixExpression(expression)
    a = [1 2;3 4];
    b = [5 6;7 8];
    array(:,:,1) = a;
    array(:,:,2) = b;
    namelist = {'a','b'};
    resultStack = Stack;
    expression = strsplit(expression);
    for i=1:length(expression)
       switch expression{i}
           case {'--'}
               [resultStack,value] = resultStack.pop();
               value = - value;
               resultStack = resultStack.push(value);
           case {'ln'}
               [resultStack,value] = resultStack.pop();
               value = log(value);
               resultStack = resultStack.push(value);
           case {'lg'}
               [resultStack,value] = resultStack.pop();
               value = log10(value);
               resultStack = resultStack.push(value);
           case {'^'}
               [resultStack,latter] = resultStack.pop();
               [resultStack,former] = resultStack.pop();
               value = former ^ latter;
               resultStack = resultStack.push(value);
           case {'+'}
               [resultStack,latter] = resultStack.pop();
               [resultStack,former] = resultStack.pop();
               value = former + latter;
               resultStack = resultStack.push(value);
           case {'-'}
               [resultStack,latter] = resultStack.pop();
               [resultStack,former] = resultStack.pop();
               value = former - latter;
               resultStack = resultStack.push(value);
           case {'*'}
               [resultStack,latter] = resultStack.pop();
               [resultStack,former] = resultStack.pop();
               value = former * latter;
               resultStack = resultStack.push(value);
           case {'/'}
               [resultStack,latter] = resultStack.pop();
               [resultStack,former] = resultStack.pop();
               value = former / latter;
               resultStack = resultStack.push(value);
           case {'e'}
               resultStack = resultStack.push(exp(1));
           otherwise
               %{
               增加运行时变量的获取方法
               %}
               valueOfVariable = getvalueOfVariable(expression{i},namelist,array);
               if ~isnan(str2double(expression{i}))
                   resultStack = resultStack.push(str2double(expression{i}));
               elseif ~isempty(valueOfVariable)
                   resultStack = resultStack.push(valueOfVariable);
               end
       end
    end
end
%{
根据字符串索引来获取变量的值
%}
function valueOfVariable = getvalueOfVariable(strname,namelist,valuematrix)
    valueOfVariable = valuematrix(:,:,ismember(namelist,strname));
end
function postfixExp = transformPostfixExpression(expression)

    %{
    去除空格
    %}
    expression = replace(expression,' ','');
    %{
    加空格, 以便遍历所有字符
    %}
    tempExp = '';
    for i=1:length(expression)
        if expression(i) == '+' || expression(i) == '-' || expression(i) == '*' || expression(i) == '/' || expression(i) == '(' || expression(i) == ')' || expression(i) == '^'
            tempExp = [tempExp,' ',expression(i),' '];
        else
            tempExp=[tempExp,expression(i)];
        end
    end
    expression = tempExp;
    %{
    去除首尾可能的空格
    %}
    expression = strtrim(expression);
    expression = strsplit(expression,' ');
    %{
    转换成后缀表达式
    %}
    opStack = Stack;
    postfixExp = '';
    for i=1:length(expression)
        switch expression{i}
           case {'e','E'}
               postfixExp = [postfixExp,'e '];
           case '('
               opStack = opStack.push('(');
           case ')'
               if opStack.stackismember('(')
                   [opStack, op] = opStack.pop();
                   while op ~= '('
                        postfixExp = [postfixExp,op,' '];
                        [opStack, op] = opStack.pop();
                   end
               else
                   break
               end
           case '-'
               %{
                区别负号和减号，只要'-'前面有数字即为减号，其他皆为负号。负号用'--'代替
               %}
               if i == 1
                   opStack = opStack.push('--');
               elseif strcmp(expression{i-1}, '+') || strcmp(expression{i-1}, '-') || strcmp(expression{i-1}, '*') || strcmp(expression{i-1}, '/') || strcmp(expression{i-1}, '(') || strcmp(expression{i-1}, '^')
                     %{
                        按负号处理，例如e^-1，1/-3
                     %}
                     opStack = opStack.push('--');
               else
                   while ~opStack.stackisempty()
                       if strcmp(opStack.getTop() ,'(')
                           opStack = opStack.push('-');
                           break
                       elseif strcmp(opStack.getTop() ,'--')|| strcmp(opStack.getTop(), '^')|| strcmp(opStack.getTop(), '*')|| strcmp(opStack.getTop(), '/')|| strcmp(opStack.getTop() ,'ln') || strcmp(opStack.getTop() ,'lg')|| strcmp(opStack.getTop(), '+') || strcmp(opStack.getTop(), '-')
                            [opStack, op] = opStack.pop();
                            postfixExp = [postfixExp,op,' '];
                       else
                           opStack = opStack.push('-');
                           break
                       end
                   end
                   if opStack.stackisempty()
                       opStack = opStack.push(expression{i});
                   end
               end
           case '+'
               %{
                忽略一些代表正号的情况，例如ln(+5), e^+5
               %}
               if i==1 || strcmp(expression{i-1}, '+') || strcmp(expression{i-1}, '-') || strcmp(expression{i-1}, '*') || strcmp(expression{i-1}, '/') || strcmp(expression{i-1}, '(') || strcmp(expression{i-1}, '^')
                   break
               else

                   while ~opStack.stackisempty()
                       if strcmp(opStack.getTop(), '(')
                           opStack = opStack.push('+');
                           break
                       elseif strcmp(opStack.getTop(), '--')|| strcmp(opStack.getTop(), '^')|| strcmp(opStack.getTop(), '*')|| strcmp(opStack.getTop(), '/')|| strcmp(opStack.getTop() ,'ln') || strcmp(opStack.getTop() ,'lg')|| strcmp(opStack.getTop(), '+') || strcmp(opStack.getTop(), '-')
                            [opStack, op] = opStack.pop();
                            postfixExp = [postfixExp,op,' '];
                       else
                           opStack = opStack.push('+');
                           break
                       end

                   end
                   if opStack.stackisempty()
                       opStack = opStack.push(expression{i});
                   end
               end
           case {'*','/'}
               while ~opStack.stackisempty()
                       if strcmp(opStack.getTop(), '(')
                           opStack = opStack.push(expression{i});
                           break
                       elseif strcmp(opStack.getTop(), '--')|| strcmp(opStack.getTop(), '^')|| strcmp(opStack.getTop(), '*')|| strcmp(opStack.getTop(), '/')|| strcmp(opStack.getTop() ,'ln') || strcmp(opStack.getTop() ,'lg')
                            [opStack, op] = opStack.pop();
                            postfixExp = [postfixExp,op,' '];
                       else
                           opStack = opStack.push(expression{i});
                           break
                       end

               end
               if opStack.stackisempty()
                    opStack = opStack.push(expression{i});
               end
            case {'ln','lg'}
                while ~opStack.stackisempty()
                       if strcmp(opStack.getTop(), '(')
                           opStack = opStack.push(expression{i});
                           break
                       elseif strcmp(opStack.getTop(), '--')|| strcmp(opStack.getTop() ,'ln') || strcmp(opStack.getTop() ,'lg')
                            [opStack, op] = opStack.pop();
                            postfixExp = [postfixExp,op,' '];
                       else
                           opStack = opStack.push(expression{i});
                           break
                       end

                end
                if opStack.stackisempty()
                    opStack = opStack.push(expression{i});
                end
            case {'^'}
                while ~opStack.stackisempty()
                       if strcmp(opStack.getTop(), '(')
                           opStack = opStack.push(expression{i});
                           break
                       elseif strcmp(opStack.getTop(), '--')|| strcmp(opStack.getTop() ,'ln') || strcmp(opStack.getTop() ,'lg') || strcmp(opStack.getTop(), '^')
                            [opStack, op] = opStack.pop();
                            postfixExp = [postfixExp,op,' '];
                       else
                           opStack = opStack.push(expression{i});
                           break
                       end

                end
                if opStack.stackisempty()
                    opStack = opStack.push(expression{i});
                end
            otherwise
                postfixExp = [postfixExp,expression{i},' '];
        end
    end
    %{
    将栈中剩余的运算符弹出
    %}

    while ~opStack.stackisempty()
        [opStack, op] = opStack.pop();
        postfixExp = [postfixExp,op,' '];
    end
end
分享