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

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

一、说明

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 <bits/stdc++.h>
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);}elseoperand_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;}elseprev = 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<<num1<<op<<num2<<"="<<val<<endl;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;
}

四、测试结果