#include <iostream>
#include <string>
#include <stack>
using namespace std;
int result;
stack<int> fix;
stack<char> opera;
string infixExp;
string postfixExp;
// 检查是否为数字
int isNum(char num)
{
if (num >= '0' && num <= '9')
return 1;
return 0;
}
// 检查是否为运算符
int isOpera(char opera)
{
string str = "+-*/()";
return str.find(opera) + 1;
}
// 检查是否满足入栈条件
int check(char op)
{
/*
入栈条件
1.栈为空
2.目标运算符或栈顶运算符为左括号
3.目标运算符优先级高于栈顶运算符优先级
*/
if (opera.empty())
return 1;
if (opera.top() == '(' || op == '(')
return 1;
if (opera.top() == '+' || opera.top() == '-')
if (op == '*' || op == '/')
return 1;
return 0;
}
// 栈内的计算
int calc(int x, int y, char opera)
{
switch (opera)
{
case '+':return y + x;
case '-':return y - x;
case '*':return y * x;
case '/':return y / x;
}
}
// 中缀表达式转后缀表达式
string calcPostfixExp()
{
// 中缀表达式的扫描
for (int i = 0; i < infixExp.size(); i++)
{
if (isNum(infixExp[i]))
{
while (isNum(infixExp[i]))
postfixExp += infixExp[i++];
postfixExp += " ";
}
// 修补中缀表达式中含负值的情况
else if (infixExp[i] == '-' && (i == 0 || isOpera(infixExp[i - 1])) && isNum(infixExp[i + 1]))
{
postfixExp += infixExp[i++];
while (isNum(infixExp[i]))
postfixExp += infixExp[i++];
postfixExp += " ";
}
if (infixExp[i] == ')')
{
while (opera.top() != '(')
{
/*
逆天特性?
代码没有作用...
postfixExp += opera.top() + " ";
代码正常运行...
postfixExp = postfixExp + opera.top() + " ";
*/
postfixExp = postfixExp + opera.top() + " ";
opera.pop();
}
opera.pop();
}
else if (check(infixExp[i]))
opera.push(infixExp[i]);
else
{
while (!opera.empty() && !check(infixExp[i]))
{
postfixExp = postfixExp + opera.top() + " ";
opera.pop();
}
opera.push(infixExp[i]);
}
}
// 中缀表达式扫描完毕,清空栈内运算符
while (!opera.empty())
{
postfixExp = postfixExp + opera.top() + " ";
opera.pop();
}
return postfixExp;
}
// 后缀表达式的计算
int calcResult()
{
for (int i = 0; postfixExp[i] != '\0'; i++)
{
if (postfixExp[i] == ' ')
continue;
// 字符串转数字并入栈
if (isNum(postfixExp[i]))
{
int n = 0;
while (isNum(postfixExp[i]))
n = n * 10 + (postfixExp[i++] - '0');
i--;
fix.push(n);
}
// 修补中缀表达式中含负值的情况
else if (postfixExp[i] == '-' && isNum(postfixExp[i + 1]))
{
i++;
int n = 0;
while (isNum(postfixExp[i]))
n = n * 10 + (postfixExp[i++] - '0');
i--;
fix.push(-n);
}
// 弹出栈顶两个元素进行计算
else
{
int x = fix.top();
fix.pop();
if (!fix.empty())
{
int y = fix.top();
fix.pop();
fix.push(calc(x, y, postfixExp[i]));
}
// 修补中缀表达式 -(x+y) 的情况
else
{
if (postfixExp[i] == '-')
fix.push(-x);
else
fix.push(x);
}
}
}
result = fix.top();
fix.pop();
return result;
}
int main()
{
cout << "中缀表达式:";
cin >> infixExp;
cout << endl << "后缀表达式:" << calcPostfixExp() << endl;
cout << endl << "计算结果:" << calcResult() << endl;
}