0

我需要实现中缀到后缀的转换算法来计算表达式 a+b*cd/e

我还需要使用队列来执行此操作（我相信需要 2 个不同的队列堆栈）

我已经使用 DoubleLinkList 创建了我的队列类，现在只需要为这个问题创建算法。不过，我很不知道该怎么做。任何帮助，将不胜感激！

到目前为止（我知道这是非常错误的）我有：

string infix = "a+b*c-d/e";
    Queue *holder = new Queue();
    Queue *newstring = new Queue();
    int length = infix.length();
    char temp;
    char prev;
    for(int i=0; i<length; i++)
    {
        temp = infix[i];
        if((temp == '+') || (temp == '-') || (temp == '*') || (temp == '/'))
        {
            if (holder->isEmpty())
            {
                holder->queue(temp);
            }
            if(temp<holder.enqueue())
            {

            }
        }
        holder->queue(temp);

    }
4

2 回答 2

2

我认为这是一项家庭作业，因此您自己弄清楚编程细节很重要。该算法的大致轮廓如下：

Define a stack
Go through each character in the string
If it is between 0 to 9, append it to output string.
If it is left brace push to stack
If it is operator *+-/ then 
          If the stack is empty push it to the stack
          If the stack is not empty then start a loop:
                             If the top of the stack has higher precedence
                             Then pop and append to output string
                             Else break
                     Push to the stack

If it is right brace then
            While stack not empty and top not equal to left brace
            Pop from stack and append to output string
            Finally pop out the left brace.

If there is any input in the stack pop and append to the output string.
于 2013-03-14T17:36:24.677 回答
0

我认为您应该创建一个运算符和值树。
您可以根据树的遍历顺序从中缀转换为后缀再到前缀。
您的讲师可能已经给您分配了在这三者之间进行转换的作业。

以下是一些文章：
德克萨斯大学
YouTube 视频
Wikipedia - 表达式树

于 2013-03-14T20:33:13.663 回答