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

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

    一、说明

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

    2. 支持的运算符包括：

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

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

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

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

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

    二、算法原理&步骤

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

    步骤：

    1. 初始化两个空堆栈，一个存放操作数，一个存放运算符。
    2. 初始化一个Map，用于存储运行过程中的变量。
    3. 找到表达式中 '=‘和’,‘的位置，‘，’会被视为两个完整语句，‘=’会将左边和右边的分隔开来，’='左边作为待赋值的变量，‘=’右边视为待求值的表达式。
    4. . 对于每个表达式，从左至右扫描输入字符串，依次读取。
    • 4.1 若为操作数，则压入操作数栈；
    • 4.2 若为字母开头，则继续扫描，到下一个字母为操作符为止，都被视为变量，在Map中查找该变量的值，压入操作数栈。
    • 4.2 若为运算符，判断其优先级是否大于运算符栈栈顶元素优先级。若大于栈顶元素优先级，则直接压栈；否则，弹出栈顶元素operator，同时依次从操作数栈中弹出两个元素number1,number2，计算表达式(number2 operator number1)的值value，并将值value压入操作数栈。重复上述过程直至当前扫描的操作符优先级大于栈顶元素，然后将当前运算符压栈。

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

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

    三、代码

    #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

    四、测试结果

    image-20220918112217717

    image-20220918112224791

  • 相关阅读:
    VM501开发套件开发版单振弦式传感器采集模块岩土工程监测
    Apache服务Rwrite功能使用
    卷积层参数个数计算公式,卷积操作的计算复杂度
    数据沿袭是止痛药还是维生素？
    详解Unity中的Nav Mesh新特性|导航寻路系统 (三)
    应用软件安全编程--18预防存储型 XSS
    多云加速云原生数仓生态，华为与 HashData 联合打造方案
    spring aop
    家政上门系统源码，家政上门预约服务系统开发涉及的主要功能
    使用Java根据约定格式生成Oracle建表语句
  • 原文地址：https://blog.csdn.net/matafeiyanll/article/details/126915482