主要思路： 用两个栈来维护进行计算： 一个栈放运算符(“±*/(”), 一个栈放数字
// 如何判断'+'或'-'是加减还是正负？ // 用一个变量来判断：数字和运算符是交替出现的（括号的出现不会影响这种交替关系） #include <iostream> #include <stack> using namespace std; string mp = "+-*/)]}"; // 没有左括号 void doCal(stack<double> &st, stack<char> &so) { //数字栈中弹出的两个元素，谁减谁，这里顺序错了 //double a=st.top();//第一次弹出的应该是要减去的值 double b = st.top(); st.pop(); double a = st.top(); st.pop(); // 运算符 char ch = so.top(); so.pop(); if (ch == '+') a = a + b; else if (ch == '-') a = a - b; else if (ch == '*') a = a * b; else if (ch == '/') a = a / b; st.push(a); return; } bool cmp(char c1, char c2) { if (c1 == '(') { return false; // 因为所有左括号统一成(压入，遇到(,c2是什么运算符都继续压入栈，不是弹出栈顶，做运算 } // 默认c1优先级<c2, 所以返回false, c2入栈 else if ((c1 == '+' || c1 == '-') && (c2 == '*' || c2 == '/')) { return false; } return true; // c2运算 } int main() { string s; while (getline(cin, s)) { stack<double> st; // 数字栈 stack<char> so; // 运算符栈 so.push('('); s += ')'; bool IsOp = false; //第一次一定是数字 for (int i = 0; i < s.size(); i++) { // 妈的这个括号，调bug半天 if (s[i] == '(' || s[i] == '[' || s[i] == '{') { so.push('('); } else if (s[i] == ')' || s[i] == ']' || s[i] == '}') { while (so.top() != '(') { doCal(st, so); } so.pop(); // 此时so.top()='(', 将‘(’出栈 } // 遇到四则运算符：前面的两个判断已经把括号的情况去除了 else if (IsOp) { // 比较当前运算符和栈顶优先级,栈顶此刻只有两种可能： // 在（和运算符+ -*/中，若栈顶优先级高，运算 while (cmp(so.top(), s[i])) { doCal(st, so); } // 当前优先级高，入栈 so.push(s[i]); IsOp = false; // 一个运算符结束后一定是数字 } // 遇到运算符和数字，找到运算符数字长度，从字符串中截取，还原数字然后压入栈中 // 只有 +33 与 -33才能进入这个循环 else { int j = i; // i=0 if (s[j] == '-' || s[j] == '+') { i++; // 运算符的索引位置为j, i=1定位数字的索引位置 } // 这个是啥意思啊，看不懂：即没找到 +33，到33时都为mp.npos,所以i++=3 while (mp.find(s[i]) == mp.npos) // 找不到就i++ { i++; // i=3, 直到找到一个数字之后的运算符就退出 } string t = s.substr(j, i - j); // substr(10, 12-10) st.push((double)stoi(t)); // stoi(string)=int, eg: stoi(-4)=-4 i--; IsOp = true; // 数字之后一定是( 或者 四则运算符 } } cout << st.top() << endl; } return 0; }