粗糙的实现,能够完成“12*3+4*11/(2-5)*2”之类的整形运算。方法是通过两个栈,一个记录操作数,一个记录操作符,然后用map记录优先级。/和*的优先级要一样,否则会有4*11/2是22还是20这样的错误。括号的处理是"("入栈,")"开始回退到"("。因为除号的两个操作数有顺序,弹出栈的时候要注意。
#include <iostream> #include <string> #include <stack> #include <vector> #include <map> using namespace std; // case: // 1+2*3+5-6/7 = 12 // 12*3+4*11/2-5*2 = 48 // 1+2*((3+(5-6)/1)+6)*3 = 49 // 12*3+4*11/(2-5)*2 = 8 map<char, int> pmap; // priority_map void init() { pmap.insert(make_pair('#', 0)); pmap.insert(make_pair('+', 1)); pmap.insert(make_pair('-', 1)); pmap.insert(make_pair('*', 2)); pmap.insert(make_pair('/', 2)); } int get_pri(char c) { if (pmap.count(c) != 0) { return pmap[c]; } return -1; } int eval(char op, int num1, int num2) { if (op == '+') return num1 + num2; if (op == '-') return num1 - num2; if (op == '*') return num1 * num2; if (op == '/') return num1 / num2; } void operate(stack<char> &op_stack, stack<int> &num_stack) { int num2 = num_stack.top(); num_stack.pop(); int num1 = num_stack.top(); num_stack.pop(); char op = op_stack.top(); op_stack.pop(); int res = eval(op, num1, num2); num_stack.push(res); } int calc(string s) { s = s + '#'; stack<char> op_stack; stack<int> num_stack; for (int i = 0; i < s.length(); i++) { if (isdigit(s[i])) { int num = 0; int j = i; while (isdigit(s[j]) && j < s.length()) { num = num * 10 + (s[j] - '0'); j++; } num_stack.push(num); i = j - 1; } else if (s[i] == '(') { op_stack.push(s[i]); } else if (s[i] == ')') { while (op_stack.top() != '(') { operate(op_stack, num_stack); } op_stack.pop(); } else // '*', '/', '+', '-', '#' { while (!op_stack.empty() && get_pri(op_stack.top()) >= get_pri((s[i]))) { operate(op_stack, num_stack); } op_stack.push(s[i]); } } return num_stack.top(); } int main() { init(); int c = calc("12*3+4*11/(2-5)*2"); cout << c << endl; }