标签：ch,return,notation,top,波兰,应用,push,表达式,op From： https://blog.csdn.net/Star_Never/article/details/143115191#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
bool parenthesisMatching(const string ¬ation);
bool isNum(char ch);
int opPriority(char ch);
double calculate(const string &s);
// reverse Polish notation 逆波兰表达式-中缀转后缀
// 进符号栈条件
/*
1.栈空
2.op优先级更高
3.左括号 （注：右括号不进）
*/
bool reversePolishNotation(const string ¬ation, string &target)
{
stack<char> op;
if (!parenthesisMatching(notation))
return false;
for (char ch : notation)
{
if (isNum(ch))
target.push_back(ch);
else
{
if (op.empty() || (!op.empty() && opPriority(ch) > opPriority(op.top())) || ch == '(')
op.push(ch);
else if (ch == ')')
{
while (op.top() != '(')
{
target.push_back(op.top());
op.pop();
}
op.pop();
}
else
{
while (!op.empty() && opPriority(ch) <= opPriority(op.top()))
{
target.push_back(op.top());
op.pop();
}
op.push(ch);
}
}
}
while (!op.empty())
{
target.push_back(op.top());
op.pop();
}
return true;
}
// parenthesis matching 括号匹配
bool parenthesisMatching(const string ¬ation)
{
stack<char> par;
for (char ch : notation)
{
if (ch == '(' || ch == '[' || ch == '{')
par.push(ch);
else if (ch == ')' || ch == ']' || ch == '}')
{
if (par.empty())
return false;
char c = par.top();
par.pop();
if ((c == '(' && ch != ')') || (c == '[' && ch != ']') || (c == '{' && ch != '}'))
return false;
}
}
return par.empty();
}
bool isNum(char ch)
{
if (ch >= '0' && ch <= '9')
return true;
return false;
}
int opPriority(char ch)
{
if (ch == '+' || ch == '-')
return 1;
if (ch == '*' || ch == '/')
return 2;
return 0;
}
double calculate(const string &s)
{
string polish;
reversePolishNotation(s, polish);
stack<double> notation;
for (char ch : polish)
{
if(!isNum(ch))
{
double x = notation.top()-'0';
notation.pop();
double y = notation.top()-'0';
notation.pop();
if (ch == '+')
notation.push(x + y);
if (ch == '-')
notation.push(x - y);
if (ch == '*')
notation.push(x * y);
if (ch == '/')
notation.push(x / y);
}
else
notation.push(ch);
}
return notation.top();
}