#include #include #include #include using namespace std;
//判断是否为操作符 bool isOperator(char op) { return (op == '+' || op == '-' || op == '*' || op == '/'); }
//判断是否为数字 bool isDigit(char op) { return (op >= '0' && op <= '9'); }
//计算表达式结果 int cal(int left, int right, char op) { int res = 0; if (op == '+') res = left + right; else if (op == '-') res = left - right; else if (op == '*') res = left * right; else if (op == '/') res = left / right; return res; }
//判断运算符优先级 int pirority(char op) { if (op == '+' || op == '-') return 1; if (op == '*' || op == '/') return 2; else return 0; }
//逆波兰表达式转中缀表达式 int evalRPN(string &tokens) { if (tokens.size() <= 0) return 0; stack s1;//创建辅助栈 int left = 0, right = 0;//定义左/右操作数 int result = 0;//定义中间结果 string temp; for (unsigned int i = 0; i < tokens.size(); i++ ) {
if (isDigit(tokens[i]))//扫描数字入栈
{
temp.push_back(tokens[i]);
}
else if (tokens[i] == ' ')
{
if (temp.size() > 0) //防止运算符后面跟分隔符，所以判断一下temp里面是否有数字
{
s1.push(atoi(temp.c_str()));
temp.clear();
}
}
else if (isOperator(tokens[i]) && !s1.empty())
{
//防止数字后面直接跟运算符，所以这里也要判断一下temp是否还有数字没有提取出来
if (temp.size() > 0)
{
s1.push(atoi(temp.c_str()));
temp.clear();
}
right = s1.top();
s1.pop();
left = s1.top();
s1.pop();
result = cal(left, right, tokens[i]);
s1.push(result);
}
}
if (!s1.empty())
{
result = s1.top();
s1.pop();
}
return result;
}
//中缀表达式转逆波兰表达式 vector infixToPRN(const string & token) { vector v1; int len = token.size();//string的长度 if (len == 0) return v1;
stack<char> s1;//存放逆波兰式的结果
int outLen = 0;
for (int i = 0; i < len ; i++)
{
if (token[i] == ' ')//跳过空格
continue;
if (isDigit(token[i]) )//若是数字，直接输出
{
v1.push_back(token[i]);
}
else if (token[i] == '(')//如果是'('，则压栈
{
s1.push(token[i]);
}else if (token[i] == ')')//如果是')'， 则栈中运算符逐个出栈并输出，直至遇到'('。 '('出栈并丢弃
{
while (s1.top() != '(')
{
v1.push_back( s1.top());
s1.pop();
}
s1.pop();//此时栈中为')'，跳过
}
while (isOperator(token[i]))//如果是运算符
{
//空栈||或者栈顶为)||新来的元素优先级更高
if( s1.empty() || s1.top() == '(' || pirority(token[i]) > pirority(s1.top()))
{
s1.push(token[i]);// 当前操作符优先级比栈顶高， 将栈顶操作符写入后缀表达式
break;
}else
{
v1.push_back(s1.top());
s1.pop();
}
}
}
while (!s1.empty())//输入结束，将栈中剩余操作符出栈输出
{
v1.push_back(s1.top());
s1.pop();
}
return v1;
} int main() { //vector sRPN = {"4", "13", "5" , "/", "+"};//逆波兰表达式 //cout << "逆波兰表达式结果为：" << evalRPN(sRPN) <<endl;
//vector<string> fix = {"4", "+", "13", "/", "5"};//中缀表达式
string fix = "2+2*(1*2-4/2)*1";
vector<char> RPN = infixToPRN(fix);
string s_fix;
for (auto it = RPN.begin(); it != RPN.end(); it++)
{
cout << *it << " ";
s_fix += *it;
s_fix += " ";
}
cout << endl;
cout << "逆波兰表达式结果为：" << evalRPN(s_fix) << endl;
system("pause");
return 0;
}