c++实现中缀表达式 转换为后缀表达式
使用栈来计算后缀表达式的值：
9+(3 - 1)*3+10/2;
后缀表达式：所有的符号都是在运算数字的后面出现： 9 3 1 – 3 * + 10 2 / +
规则:
中缀表达式转后缀表达式:
1.从左到右遍历中缀表达式的每个数字和符号，若是数字就打印同时入栈数字栈snum；
2.若是左括号，则将其压入运算符栈sope中；
3.若是右括号，则将sope栈顶的运算符弹出并打印，直到遇到左括号（左括号也出栈，但不输出打印）；
4.若是运算符，若该运算符的优先级大于栈顶运算符的优先级时，则把它压栈；若小于或等于栈顶运算符优先级时，则将栈顶运算符弹出并打印, 同时出栈snum数字按照此运算符运算后结果入栈，再比较新的栈顶运算符，按同样方法处理，直到该运算符大于栈顶运算符优先级为止，然后将该运算符压栈；
5.若中缀表达式中的各对象处理完毕，则把sope栈中存留的运算符依次弹栈输出打印, 同时取snum中的值按照此运算符运算后的结果入栈,直至sope栈空 。snum栈底元素出栈即为计算结果。
计算规则:
- 创建一个双精度数字栈
snum来存储操作数。Copy- 使用
stringstream将输入字符串postfix便于逐个提取 token。- 使用
while (ss >> token)循环来逐个读取 token，直到字符串流结束。每次读取都会跳过空格。- 如果 token 的第一个字符是数字（使用
isdigit函数判断），则将这个 token 转换为double类型并推入栈中。- 如果 token 不是数字，说明它是一个操作符。
- 从栈中弹出两个元素（x 和 y），注意：弹出顺序是后进先出（LIFO），所以首先弹出的将是最近进入栈的数字
- 根据操作符执行相应的数学运算，并将计算结果压入栈中。
- 针对除法，还需检查除数
y是否为零，如果是，则抛出异常以避免除以零错误。- 最后，函数返回栈顶元素，这个值是后缀表达式的计算结果.
完整代码:
#include <iostream>
#include <string>
#include <exception>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
bool isvalidexpression(const string & expression)
{
for (char ch : expression)
{
if (!isdigit(ch) && ch != '+' && ch != '-' && ch != '*' && ch != '/' && ch != ' ')
{
return false;
}
}
return true;
}int precedence(char ch)
{
switch (ch)
{
case '+':
case'-':
return 1;
case '*':
case '/':
return 2;
default:
return 0;}
}string infixtopostfix(const string& expression)
{
stack<char> sope;//字符栈
string postfix = "";//后缀表达式
string numbuff = "";
for (size_t i = 0; i < expression.length(); i++)
{
char ch = expression[i];
if (isdigit(ch))
{
numbuff += ch;
}
else
{
if (!numbuff.empty())
{
postfix += numbuff;
postfix += ' ';
numbuff.clear();
}
if (ch == '(')
{
sope.push(ch);
}
else if (ch == ')')
{
while (!sope.empty() && sope.top() != '(')
{
postfix += sope.top();
postfix += ' ';
sope.pop();
}
sope.pop();//出栈'('
}
else
{
while (!sope.empty() && precedence(sope.top()) >= precedence(ch))
{
postfix += sope.top();
postfix += ' ';
sope.pop();
}
sope.push(ch);
}
}
}
if (!numbuff.empty())
{
postfix += numbuff;
postfix += ' ';
}
while (!sope.empty())
{
postfix += sope.top();
postfix += ' ';
sope.pop();
}if (!postfix.empty() && postfix.back() == ' ')
{
postfix.pop_back();
}
return postfix;}
double evaluatepostfix(const string& postfix)
{
stack<double>snum;//数字栈
stringstream ss(postfix);
string token;
while (ss >> token)
{
if (isdigit(token[0]))
{
snum.push(stod(token));//stod是一个函数，用于将字符串转换为double类型的浮点数。
}
else
{
double x = snum.top(); snum.pop();
double y = snum.top(); snum.pop();
switch (token[0])
{
case '+':snum.push(x + y); break;
case'-':snum.push(x - y); break;
case '*':snum.push(x * y); break;
case '/':if (y != 0)
{
snum.push(x / y);
}
else
{
throw runtime_error("Error:Division By Zero");
}
break;
}
}
}return snum.top();
}int main()
{
//输入一个表达式
string expression;
cout << "请输入一个算数表达式:(例如2*3*(4+5))" << endl;
getline(cin , expression);//检测有效性
if (!isvalidexpression(expression))
{
cout << "表达式不合法" << endl;
}
//将中缀表达式转换为后缀表达式
string postfix = infixtopostfix(expression);
cout << "后缀表达式是:"<<postfix << endl;//计算后缀表达式的值
try
{
double result = evaluatepostfix(postfix);
cout << "后缀表达式的结果为:" << result << endl;
}
catch (runtime_error& e)
{
cout << e.what() << endl;
}system("pause");
return 0;
}