数据结构与算法 中缀表达式转后缀表达式
花了一天半 终于把中缀表达式转后缀表达式的代码写了出来 特地发此贴给各位作为参考有优化建议各位可以提出
#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 = 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;
while (index < this->InfixExpression.length())
{
if (isOperator(this->InfixExpression))
{
// 4.遇到符号 将其压入符号栈 并于其栈顶的符号进行比较
compare(this->InfixExpression);
index++;
}
else if (this->InfixExpression == '(' || this->InfixExpression == ')')
{
/*
5.遇到括号时
(1).如果是左括号"(" 则直接压入栈
(2).如果是右括号")" 则依次弹出符号栈中的栈顶符号并压入表达式栈 直到遇到左括号"("停止
*/
if (this->InfixExpression == '(')
{
this->operatorStack.push(InfixExpression);
}
else
{
while (operatorStack.top() != '(')
{
this->expressionStack = operatorStack.top();
operatorStack.pop();
this->expressionStackIndex++;
}
operatorStack.pop();
}
index++;
}
else
{
while (!isOperator(this->InfixExpression) && this->InfixExpression >= '0' && this->InfixExpression <= '9')
{
number += this->InfixExpression;
index++;
}
this->expressionStack = number;
this->expressionStackIndex++;
number = "";
}
}
/* 7.将符号栈中的剩余的符号依次弹出并压入表达式栈
8.依次弹出表达式栈 结果的逆序即为中缀表达式的后缀表达式*/
while (!this->operatorStack.empty())
{
this->expressionStack = operatorStack.top();
operatorStack.pop();
this->expressionStackIndex++;
}
index = 0;
while (this->expressionStackIndex != index)
{
Result += this->expressionStack + " ";
index++;
}
}
int main()
{
std::string expression = "(3+4)*5-6";
IEToPE *IP = new IEToPE;
IP->bind(expression);
std::cout << expression << "==>" << IP->getResult();
return 0;
}
页:
[1]