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

临时用户3.14159

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

有优化建议各位可以提出

#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;
}