题解 | #表达式求值#
表达式求值
http://www.nowcoder.com/practice/9566499a2e1546c0a257e885dfdbf30d
思路:
- 将表达式转为逆波兰式;
- 计算逆波兰式的值。
PS:默认表达式中不含空格。
#include <iostream> #include <string> #include <stack> using namespace std; // 通过一个单调栈(存储操作符)将表达式转为逆波兰式 string trans(string exp) { stack<char> opt_stk; int idx = 0, len = exp.length(); string ans; char num_sign = '#'; while (idx < len) { switch (exp[idx]) { case '(': opt_stk.push('('); idx++; break; case ')': while (opt_stk.top() != '(') { ans += opt_stk.top(); opt_stk.pop(); } opt_stk.pop(); idx++; break; case '+': case '-': // 以下两种情况将负号视作符号位,不将其入栈 // 1. 负号在第一位 // 2. 负号前一位字符不是数字,也不是反括号 if (exp[idx] == '-' && (idx == 0 || (idx > 0 && exp[idx-1] != ')' && !isdigit(exp[idx-1])))) { num_sign = '@'; idx++; } else { while (!opt_stk.empty() && opt_stk.top() != '(') { ans += opt_stk.top(); opt_stk.pop(); } opt_stk.push(exp[idx++]); } break; case '*': case '/': while (!opt_stk.empty()) { char c = opt_stk.top(); if (c == '*' || c == '/') { ans += c; opt_stk.pop(); } else break; } opt_stk.push(exp[idx++]); break; default: while (idx < len && exp[idx] <= '9' && exp[idx] >= '0') ans += exp[idx++]; ans += num_sign; if (num_sign == '@') num_sign = '#'; } } while (!opt_stk.empty()) { ans += opt_stk.top(); opt_stk.pop(); } return ans; } // 也只用一个栈,栈中存放的是操作数 double compute_value(string exp) { stack<double> stk; int idx = 0, len = exp.length(); while (idx < len) { char c = exp[idx]; if (c == '+') { double a = stk.top(); stk.pop(); double b = stk.top(); stk.pop(); stk.push(a + b); } else if (c == '-') { double a = stk.top(); stk.pop(); double b = stk.top(); stk.pop(); stk.push(b - a); } else if (c == '*') { double a = stk.top(); stk.pop(); double b = stk.top(); stk.pop(); stk.push(a * b); } else if (c == '/') { double a = stk.top(); stk.pop(); double b = stk.top(); stk.pop(); stk.push(b / a); } else { double num = 0; while (exp[idx] <= '9' && exp[idx] >= '0') num = num * 10 + exp[idx++] - '0'; if (exp[idx] == '@') num = -num; stk.push(num); } idx++; } return stk.top(); } int main() { string exp; cin >> exp; // cout << trans(exp) << endl; cout << compute_value(trans(exp)); return 0; }