数据结构与算法中缀表达式转后缀表达式

临时用户3.14159 · 发表于 2022-2-2 13:50:25

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

花了一天半终于把中缀表达式转后缀表达式的代码写了出来特地发此贴给各位作为参考

有优化建议各位可以提出

#include <iostream>
#include <string>
#include <stack>
/*
1.初始化两个栈一个符号栈(operatorStack) 另一个表达式栈(expressionStack)
2.定义一个指针(索引)index 从左至右扫描中缀表达式
3.遇到数字将其压入表达式栈(
4.遇到符号将其压入符号栈并于其栈顶的符号进行比较
(1).如果符号栈为空或栈顶的符号为"(" 则直接将当前符号压入栈
(2).否则，若当前符号的优先级比栈顶符号的优先级高则将当前的符号压入栈
(3).若当前符号的优先级比栈顶符号低或相等则将栈顶符号弹出压入表达式栈再转到4.1与符号栈中的新的栈顶符号进行比较
5.遇到括号时
(1).如果是左括号"(" 则直接压入栈
(2).如果是右括号")" 则依次弹出符号栈中的栈顶符号并压入表达式栈直到遇到左括号"("停止
6.重复2 - 5 的步骤直到表达式的末尾
7.将符号栈中的剩余的符号依次弹出并压入表达式栈
8.依次弹出表达式栈结果的逆序即为中缀表达式的后缀表达式
*/
class IEToPE //中缀表达式(IndixExpression)转后缀表达式类
{
public:
void bind(std::string);
std::string getResult() const;
private:
void ToPe(); //最主要的处理函数
bool isOperator(char); //符号判断目前支持"+" "-" "*" "/"
int operatorPriority(char); //符号优先级判断
void compare(char data); //用于运算符处理
std::string Result; //中缀表达式转后缀表达式的结果用gerResult()函数获取
std::string InfixExpression; //中缀表达式
std::stack<char> operatorStack;//符号栈
std::string* expressionStack; //表达式栈
int expressionStackIndex;
};
std::string IEToPE::getResult() const
{
if(InfixExpression.empty())
{
return NULL;
}
return Result;
}
void IEToPE::compare(char data)
{
// 4.遇到符号将其压入符号栈并于其栈顶的符号进行比较
// (1).如果符号栈为空或栈顶的符号为"(" 则直接将当前符号压入栈
// (2).否则，若当前符号的优先级比栈顶符号的优先级高则将当前的符号压入栈
// (3).若当前符号的优先级比栈顶符号低或相等则将栈顶符号弹出压入表达式栈再转到4.1与符号栈中的新的栈顶符号进行比较
if (this->operatorStack.empty() || (operatorStack.top() == '(')) //(1).如果符号栈为空或栈顶的符号为"(" 则直接将当前符号压入栈
{
operatorStack.push(data);
}
else if (this->operatorPriority(data) > this->operatorPriority(this->operatorStack.top()))
{ //(2).否则，若当前符号的优先级比栈顶符号的优先级高则将当前的符号压入栈
operatorStack.push(data);
}
else
{ //(3).若当前符号的优先级比栈顶符号低或相等则将栈顶符号弹出压入表达式栈再转到4.1与符号栈中的新的栈顶符号进行比较
expressionStack[expressionStackIndex] = operatorStack.top();
operatorStack.pop();
expressionStackIndex++;
this->compare(data);
}
}
int IEToPE::operatorPriority(char data)
{
if (data == '*' || data == '/')
{
return 1;
}
else if (data == '+' || data == '-')
{
return 0;
}
else
{
return -1;
}
}
bool IEToPE::isOperator(char Operator)
{
return (Operator == '+' || Operator == '-' || Operator == '*' || Operator == '/');
}
void IEToPE::bind(std::string InfixExpression)
{
this->InfixExpression = InfixExpression;
ToPe();
}
void IEToPE::ToPe()
{
int index = 0;
this->expressionStackIndex = 0;
std::string number;
this->expressionStack = new std::string[128];
while (index < this->InfixExpression.length())
{
if (isOperator(this->InfixExpression[index]))
{
// 4.遇到符号将其压入符号栈并于其栈顶的符号进行比较
compare(this->InfixExpression[index]);
index++;
}
else if (this->InfixExpression[index] == '(' || this->InfixExpression[index] == ')')
{
/*
5.遇到括号时
(1).如果是左括号"(" 则直接压入栈
(2).如果是右括号")" 则依次弹出符号栈中的栈顶符号并压入表达式栈直到遇到左括号"("停止
*/
if (this->InfixExpression[index] == '(')
{
this->operatorStack.push(InfixExpression[index]);
}
else
{
while (operatorStack.top() != '(')
{
this->expressionStack[this->expressionStackIndex] = operatorStack.top();
operatorStack.pop();
this->expressionStackIndex++;
}
operatorStack.pop();
}
index++;
}
else
{
while (!isOperator(this->InfixExpression[index]) && this->InfixExpression[index] >= '0' && this->InfixExpression[index] <= '9')
{
number += this->InfixExpression[index];
index++;
}
this->expressionStack[this->expressionStackIndex] = number;
this->expressionStackIndex++;
number = "";
}
}
/* 7.将符号栈中的剩余的符号依次弹出并压入表达式栈
8.依次弹出表达式栈结果的逆序即为中缀表达式的后缀表达式*/
while (!this->operatorStack.empty())
{
this->expressionStack[this->expressionStackIndex] = operatorStack.top();
operatorStack.pop();
this->expressionStackIndex++;
}
index = 0;
while (this->expressionStackIndex != index)
{
Result += this->expressionStack[index] + " ";
index++;
}
}
int main()
{
std::string expression = "(3+4)*5-6";
IEToPE *IP = new IEToPE;
IP->bind(expression);
std::cout << expression << "==>" << IP->getResult();
return 0;
}

复制代码

账号		自动登录	找回密码
密码			立即注册

[技术交流] 数据结构与算法中缀表达式转后缀表达式

马上注册，结交更多好友，享用更多功能^_^

评分

[技术交流] 数据结构与算法 中缀表达式转后缀表达式

马上注册，结交更多好友，享用更多功能^_^

评分

[技术交流] 数据结构与算法中缀表达式转后缀表达式