表达式求值

 

表达式求值 - OI Wiki

只含左结合的二元运算符的含括号表达式:

创建一个操作栈op, 数字栈st, 遍历整个表达式 若

1.左括号, 直接入op栈

2.右括号, 从栈顶一个一个拿出op进行计算, 知道遇见左括号

3.如果是数字, 直接入st栈

4.如果是操作符, 当栈顶操作符优先级大于等于当前运算符优先级时, 把op栈栈顶操作符一个一个拿出来运算

也可以用这个代码来输出后缀表达式, 遇到数字, 直接加入后缀表达式字符串, 对于操作符, 加入后缀表达式即为上述计算操作

如果加上一元运算符与右结合的运算符

如果是一元运算符, 可以加上一个is_single字段, 操作之后一直改变这个字段的值, 来判断这个运算符是否为一元运算符

如果由有右结合的运算符, 比如幂操作,  把

while (!op.empty() && priority(op.top()) >= priority(cur_op)) 

 改为

while (!op.empty() &&((left_assoc(cur_op) && priority(op.top()) >= priority(cur_op)) ||(!left_assoc(cur_op) && priority(op.top()) > priority(cur_op))))

 即 如果是右运算符  把"当栈顶操作符优先级大于等于当前运算符优先级时, 把op栈栈顶操作符一个一个拿出来运算" 改为大于而不是大于等于

代码

bool delim(char c) { return c == ' '; }bool is_op(char c) { return c == '+' || c == '-' || c == '*' || c == '/'; }int priority(char op) {if (op == '+' || op == '-') return 1;if (op == '*' || op == '/') return 2;return -1;   //这一句是必要的, 会把括号的优先级返回为-1
}void process_op(stack<int>& st, char op) {  // 也可以用于计算后缀表达式int r = st.top();                         // 取出栈顶元素，注意顺序st.pop();int l = st.top();st.pop();switch (op) {case '+':st.push(l + r);break;case '-':st.push(l - r);break;case '*':st.push(l * r);break;case '/':st.push(l / r);break;}
}int evaluate(string& s) {  // 也可以改造为中缀表达式转换后缀表达式stack<int> st;stack<char> op;for (int i = 0; i < (int)s.size(); i++) {if (delim(s[i])) continue;if (s[i] == '(') {op.push('(');  } else if (s[i] == ')') { while (op.top() != '(') {process_op(st, op.top());op.pop();  }op.pop();                } else if (is_op(s[i])) {  char cur_op = s[i];while (!op.empty() && priority(op.top()) >= priority(cur_op)) {process_op(st, op.top());op.pop(); }op.push(cur_op);  } else {            int number = 0;while (i < (int)s.size() && isalnum(s[i]))number = number * 10 + s[i++] - '0';--i;st.push(number);}}while (!op.empty()) {process_op(st, op.top());op.pop();}return st.top();
}

求后缀表达式

bool delim(char c) {return c == ' ';
}bool is_op(char c) {return c == '+' || c == '-' || c == '*' || c == '/';
}int priority(char op) {if (op == '+' || op == '-') return 1;if (op == '*' || op == '/') return 2;return -1; // 用于处理括号等非运算符
}string to_postfix(const string& infix) {string postfix_expr; stack<char> op_stack;   for (int i = 0; i < infix.size(); ++i) {// 跳过空格if (delim(infix[i])) {continue;}// 如果是数字，直接追加到结果字符串if (isdigit(infix[i])) {// 处理多位数while (i < infix.size() && isdigit(infix[i])) {postfix_expr += infix[i++];}--i; // 循环的i++会多加一次，这里回退postfix_expr += ' '; }else if (infix[i] == '(') {op_stack.push('(');}// else if (infix[i] == ')') {while (!op_stack.empty() && op_stack.top() != '(') {postfix_expr += op_stack.top();postfix_expr += ' ';op_stack.pop();}if (!op_stack.empty()) {op_stack.pop(); }}else if (is_op(infix[i])) {char current_op = infix[i];while (!op_stack.empty() && priority(op_stack.top()) >= priority(current_op)) {postfix_expr += op_stack.top();postfix_expr += ' ';op_stack.pop();}op_stack.push(current_op);}}while (!op_stack.empty()) {postfix_expr += op_stack.top();postfix_expr += ' ';op_stack.pop();}if (!postfix_expr.empty()) {postfix_expr.pop_back();}return postfix_expr;
}