《C++ Primer》练习9.52：使用栈实现四则运算

在这里插入图片描述

栈可以用来使用四则运算，是一个稍微有点复杂的题目，去学习了一下用栈实现四则运算的原理，用C++实现了一下。首先要把常见的中缀表达式改成后缀表达式，然后通过后缀表达式计算，具体的原理可以参考这位博主的文章：C语言数据结构篇——用栈实现四则运算，在数和运算符之间都加入了空格来进行分隔，方便后续的提取有效数据处理。

代码还有优化的地方，先记录一下吧：

#include <iostream>
#include <string>
#include <stack>
using namespace std;int getOperatorPriority(char &a)
{int res;if (a == '(')res = 0;else if (a == '+' || a == '-')res = 1;else if (a == '*' || a == '/')res = 2;else if (a == ')')res = 3;return res;
}
bool compareOperatorPriority(char &a, char &b)
{int a_res = getOperatorPriority(a);int b_res = getOperatorPriority(b);return a_res >= b_res;
}string createBackSeq(string &str)
{stack<char> sak;string str2;int seen = 0;int p = 0;for (int i = 0; i != str.size(); ++i){if (isdigit(str[i])){str2.append(str.substr(i, 1));if ((i + 1 != str.size() && !isdigit(str[i + 1])) || i == str.size() - 1)str2.append(" ");}else{if (sak.empty()){if (str[i] == '(')seen += 1;sak.push(str[i]);}else if (str[i] == ')'){if (seen != 0){while (sak.top() != '('){str2 += sak.top();str2.append(" ");sak.pop();}sak.pop();seen--;}elsethrow std::invalid_argument("No left bracket match!");}else{if (compareOperatorPriority(sak.top(), str[i])){if (str[i] == '('){seen++;sak.push(str[i]);}else{str2 += sak.top();str2.append(" ");sak.pop();sak.push(str[i]);}}else{sak.push(str[i]);}}}}while (!sak.empty()){if (seen != 0)throw invalid_argument("too many left barckets!");str2 += sak.top();str2.append(" ");sak.pop();}return str2;
}int calculate(string &str)
{size_t pos1 = 0;size_t pos2 = 0;stack<int> b;while (pos2 != string::npos){pos1 = str.find_first_not_of(' ', pos1);pos2 = str.find_first_of(' ', pos2);if (pos2 != string::npos){string temp = str.substr(pos1, pos2 - pos1);if (temp.find_first_not_of("0123456789") == string::npos)b.push(stoi(temp));else{if (b.size() < 2)throw std::invalid_argument("too many symbols");int right = b.top();b.pop();int left = b.top();b.pop();int res;if (temp == "+")res = left + right;else if (temp == "*")res = left * right;else if (temp == "-")res = left - right;else if (temp == "/"){if (right == 0)throw std::invalid_argument("Divided by zero.");res = left / right;}b.push(res);}pos2 += 1;pos1 = pos2;}}return b.top();
}int main()
{string str;string str2;str = "22*(1+2)-(3*4)/(2*1)";str2 = createBackSeq(str);cout << str2 << endl;cout << calculate(str2) << endl;str = "1+3*(2++5)";str2 = createBackSeq(str);cout << str2 << endl;cout << calculate(str2) << endl;	return 0;
}