交互式表达式求值（支持多种类型的运算符）

交互式表达式求值（支持多种类型的运算符）

一、说明

1. 输入字符串为中缀表达式，无需转为后缀表达式

2. 支持的运算符包括：

算术运算符：“+,-,*,/”

关系运算符：“>,<,>=,<=,=,!=”(注意等于运算符采用的是一个等号)

逻辑运算符：“&&,||”

单目运算符：“++，–”

3. 支持大于10的数字，不支持负数操作数，但支持中间结果和返回值为负数
4. 支持逗号分隔表达式
5. 支持变量，程序运行期间，变量保持其值
6. 以交互方式求值，按行输入表达式，回车显示其值

二、算法原理&步骤

本文算法对中缀表达式形式字符串进行求值，同时支持与或运算和逻辑运算(若含有关系运算符或者逻辑运算符，则输出为1或者0)。类似于加减乘除，将关系运算符和逻辑运算符看作优先级低的运算符进行处理，优先级：单目运算符>算术运算符>关系运算符>逻辑运算符。

步骤：

1. 初始化两个空堆栈，一个存放操作数，一个存放运算符。
2. 初始化一个Map，用于存储运行过程中的变量。
3. 找到表达式中 '=‘和’,‘的位置，‘，’会被视为两个完整语句，‘=’会将左边和右边的分隔开来，’='左边作为待赋值的变量，‘=’右边视为待求值的表达式。
4. . 对于每个表达式，从左至右扫描输入字符串，依次读取。

• 4.1 若为操作数，则压入操作数栈；
• 4.2 若为字母开头，则继续扫描，到下一个字母为操作符为止，都被视为变量，在Map中查找该变量的值，压入操作数栈。
• 4.2 若为运算符，判断其优先级是否大于运算符栈栈顶元素优先级。若大于栈顶元素优先级，则直接压栈；否则，弹出栈顶元素operator，同时依次从操作数栈中弹出两个元素number1,number2，计算表达式(number2 operator number1)的值value，并将值value压入操作数栈。重复上述过程直至当前扫描的操作符优先级大于栈顶元素，然后将当前运算符压栈。

3. 弹出运算符栈顶元素operator，判断是单目运算符还是双目运算符，单目运算符则弹出一个操作数，否则同时依次从操作数栈中弹出两个元素number1,number2，计算表达式(number2 operator number1)的值value，并将值value压入操作数栈。重复上述过程直至运算符栈为空。

4. 此时操作数栈应该只有一个元素，即为表达式的值。

三、代码

#include 
using namespace std;
unordered_map<string,int> Map;

/* 判断字符是否属于运算符 */
bool isOperator(char c)
{
    switch (c)
    {
        case '-':
        case '+':
        case '*':
        case '/':
        case '%':
        case '<':
        case '>':
        case '=':
        case '!':
        case '&':
        case '|':
            return true;
        default:
            return false;
    }
}

/* 获取运算符优先级 */
int getPriority(string op)
{
    int temp = -1;
    if (op == "++" || op == "--")
        temp = 5;
    else if (op == "*" || op == "/" || op == "%")
        temp = 4;
    else if (op == "+" || op == "-")
        temp = 3;
    else if (op == ">" || op == "<" || op == ">=" || op == "<="
             || op == "=" || op == "!=")
        temp = 2;
    else if (op == "&&" || op == "||")
        temp = 1;
    return temp;
}
/*
 * 返回一个两元中缀表达式的值
 * syntax: num_front op num_back
 * @param num_front: 前操作数
 * @param num_back: 后操作数
 * @param op: 运算符
 */
int Calculate(int num_front, int num_back, string op)
{
    if (op == "+")
        return num_front + num_back;
    else if (op == "-")
        return num_front - num_back;
    else if (op == "*")
        return num_front * num_back;
    else if (op == "/")
        return num_front / num_back;
    else if (op == "%")
        return num_front % num_back;
    else if (op == "!=")
        return num_front != num_back;
    else if (op == ">=")
        return num_front >= num_back;
    else if (op == "<=")
        return num_front <= num_back;
    else if (op == "==")
        return num_front == num_back;
    else if (op == ">")
        return num_front > num_back;
    else if (op == "<")
        return num_front < num_back;
    else if (op == "&&")
        return num_front && num_back;
    else if (op == "||")
        return num_front || num_back;
    else if (op == "++")
        return num_front + 1;
    else if (op == "--")
        return num_front - 1;
    return 0;
}
/* 新运算符入栈操作 */
void addNewOperator(string new_op, stack<int>& operand_stack, stack<string>& operator_stack)
{
    while (!operator_stack.empty() && getPriority(operator_stack.top()) >= getPriority(new_op))
    {
        int num2 = operand_stack.top();
        operand_stack.pop();
        int num1 = operand_stack.top();
        operand_stack.pop();
        string op = operator_stack.top();
        operator_stack.pop();

        int val = Calculate(num1, num2, op);
        operand_stack.push(val);
    }
    operator_stack.push(new_op);
}

int equalpos(string input)
{
    for (int i=1;i<input.size()-1;i++){
        if(input[i]=='=' && !isOperator(input[i-1]) && !isOperator(input[i+1])){
            return i;
        }
    }
    return -1;
}

/* 字符串表达式求值
 * @param input: 输入的字符串
 * @param output: 表达式的值，若含有关系运算符则为1或者0
 * return 计算过程是否正常
 */
bool ExpValue(string input_prev,int& output)
{
    int equal_pos = equalpos(input_prev);
    string input = "";
    string var = "";
    if(equal_pos==-1) input = input_prev;
    else {
        var = input_prev.substr(0,equal_pos);
        input = input_prev.substr(equal_pos+1,input_prev.size());
    }

    stack<int> operand_stack;
    stack<string> operator_stack;

    char prev = 0; // 上一个属于运算符的字符
    for (int i = 0; i < input.size(); i++)
    {
        char c = input[i];
        // prev是否是一个完整运算符
        if (!isOperator(c) && prev)
        {
            string new_op = string("").append(1, prev);
            addNewOperator(new_op, operand_stack, operator_stack);
            prev = 0;
        }

        // 数字
        if (isdigit(c))
        {
            int val_c = c - '0';
            if (i > 0 && isdigit(input[i - 1]))
            {
                int top_num = operand_stack.top();
                top_num = top_num * 10 + val_c;
                operand_stack.pop();
                operand_stack.push(top_num);
            }
            else
                operand_stack.push(val_c);
        }

        //变量
        else if(c>='a' && c<='z' || c>='A' && c<='Z'){
            string s = ""; s = s+c;
            c = input[++i];
            while(c>='a' && c<='z' || c>='A' && c<='Z' || c>='0' && c<='9' || c=='_'){
                s += c;
                c = input[++i];
            }
            if(Map.find(s)!=Map.end()){
                operand_stack.push(Map[s]);
                i--;
            }
        }
            // 运算符字符
        else if (isOperator(c))
        {
            // 处理两字符运算符
            if (prev)
            {
                string new_op = string("").append(1, prev).append(1, c);
                addNewOperator(new_op, operand_stack, operator_stack);
                prev = 0;
            }
            else
                prev = c;
        }
        else if (c == '(')
            operator_stack.push("(");
        else if (c == ')')
        {
            // 处理括号内的运算符
            while (operator_stack.top()!="(")
            {
                int num1 = operand_stack.top();
                operand_stack.pop();
                int num2 = operand_stack.top();
                operand_stack.pop();
                string op = operator_stack.top();
                operator_stack.pop();

                int val = Calculate(num2, num1, op);
                operand_stack.push(val);
            }
            operator_stack.pop(); // 弹出"("
        }
    }
//    assert(operand_stack.size() == operator_stack.size() + 1);
    // 弹出所有运算符
    while(!operator_stack.empty())
    {
        string op = operator_stack.top();
        operator_stack.pop();
        int num1,num2;
        if(op=="++" || op=="--"){  //单目运算符
            num1 = operand_stack.top();
            operand_stack.pop();
            num2 = 0;
        }else{
            num2 = operand_stack.top();
            operand_stack.pop();
            num1 = operand_stack.top();
            operand_stack.pop();
        }

        int val = Calculate(num1, num2, op);
//        cout<
        operand_stack.push(val);
    }

    if (operand_stack.size() == 1) {
        output = operand_stack.top();
        if(var!="")
            Map[var] = output;
        return true;
    }
    return false;
}

vector<string> split(string s, char ch)
{
    vector<string> res;

    int n = s.size();
    int i = 0;

    while(i < n)
    {
        int j = i + 1;
        while(j < n && s[j] != ch) ++j;
        res.push_back(s.substr(i, j - i));
        i = j + 1;
    }
    return res;
}

void test()
{
    string s0 = "10-1*10+3%2";
    string s1 = "100 + (3-33)*2";
    string s2 = "20+1 >= 20 && 20+1 < 20";
    string s3 = "10>20 || 10/1>=5";
    string s4 = "a4=2";
    string s5 = "b=a4+3";
    string s6 = "b++";
    int ret = -1;
    if (ExpValue(s0, ret))
        cout << s0 << ": " << ret << endl;

    if (ExpValue(s1, ret))
        cout << s1 << ": " << ret << endl;

    if (ExpValue(s2, ret))
        cout << s2 << ": " << ret << endl;

    if (ExpValue(s3, ret))
        cout << s3 << ": " << ret << endl;

    if (ExpValue(s4, ret))
        cout << s4 << ": " << ret << endl;

    if (ExpValue(s5, ret))
        cout << s5 << ": " << ret << endl;

    if (ExpValue(s6, ret))
        cout << s6 << ": " << ret << endl;
}

void Interactive_Calculator()
{
    while(true){
        char *s;
        int ret = -1;
        cout<<"&";  cin>>s;
        vector<string> exprs = split(s,',');
        for(int i=0;i<exprs.size();i++){
            ExpValue(exprs[i],ret);
        }
        cout<<ret<<endl;
//        if (ExpValue(s, ret))
//            cout << ret << endl;
    }
}

int main()
{
//    test();
    Interactive_Calculator();
    return 0;
}
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
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307

四、测试结果