-1

我正在尝试编写一个简单的程序来将中缀表示法转换为前缀和后缀。到目前为止，后缀一完美。但是，我似乎无法正确转换前缀。我对两者都使用了调车场算法。如果我的代码有点不寻常（即编写自己的堆栈类而不是使用#include，不必要地使用其他东西），请事先道歉，我必须满足作业要求（这是大学作业）。这是我到目前为止所尝试的：

#include<iostream>
#include<string.h>
using namespace std;

const int Max=255;
class Stack
{
private:
    char element[Max];
    int top;
public:
    Stack()
    {
        top=-1;
    }
    bool isFull()
    {
        if(top>=(Max-1)) return true;
        else return false;
    }
    bool isEmpty()
    {
        if(top==-1) return true;
        else return false;
    }
    bool push(char x)
    {
        if(!isFull())
        {
            top++;
            element[top]=x;
            return true;
        }
        else
        {
            cout<<"Stack is full"<<endl;
            return false;
        }
    }
    bool pop(char &x)
    {
        if(!isEmpty())
        {
            x=element[top--];
            return true;
        }
        else
        {
            //cout<<"Stack is empty"<<endl;
            return false;
        }
    }
    char retrieve()
    {
        if(!isEmpty())
        {
            return element[top];
        }
        else
        {
            //cout<<"Stack is empty"<<endl;
            return ' ';
        }
    }
};


class Converter
{
private:
public:
    Converter(){}
    bool isOperator(char x)
    {
        if(x=='+'||x=='-'||x=='*'||x=='/'||x=='^'||x=='('||x==')') return true;
        else return false;
    }
    bool isOperand(char x)
    {
        if(x>='0'&&x<='9') return true;
        else return false;
    }
    int Hierarchy(char x)
    {
        if(x=='+'||x=='-') return 1;
        else if(x=='*'||x=='/') return 2;
        else if(x=='^') return 3;
        else return 0;
    }
    char*ToPostfix(char infix[])
    {
        Stack stack1;
        char res[20];
        int resindex=0;
        for(int i=0;i<strlen(infix);i++)
        {
            if(isOperator(infix[i]))
            {
                if(infix[i]=='(')
                {
                    stack1.push(infix[i]);
                }
                else if(infix[i]==')')
                {
                    while(stack1.retrieve()!='(')
                    {
                        stack1.pop(res[resindex++]);
                    }
                    stack1.pop(res[resindex]);
                }
                else 
                {
                    while(Hierarchy(infix[i])<=Hierarchy(stack1.retrieve()))
                    {
                        stack1.pop(res[resindex++]);
                    }
                    stack1.push(infix[i]);
                }
            }
            else if(isOperand(infix[i]))
            {
                res[resindex++]=infix[i];
            }
        }
        while(!stack1.isEmpty())
        {
            stack1.pop(res[resindex++]);
        }
        res[resindex]='\0';
        return res;
    }
    char*ToPrefix(char infix[])
    {
        char res[20];
        strcpy(res,strrev(infix));
        for(int i=0;i<strlen(res);i++)
        {
            if(res[i]=='(') 
            {
                res[i]=')';
            }
            else if(res[i]==')')
            {
                res[i]='(';
            }
        }
        strcpy(res,ToPostfix(res));
        strcpy(res,strrev(res));
        return res;
    }
};
int main()
{
    Converter convert;
    char infix[20];
    cout<<"Enter infix expression: ";
    cin>>infix;
    cout<<endl<<"Prefix: "<<convert.ToPrefix(infix)<<endl;
    cout<<"Postfix: "<<convert.ToPostfix(infix)<<endl;
    return 0;
}

当我尝试转换一个简单的中缀表示法，即 1*(2+3)/4^5-6 时，后缀转换是正确的 (123+*45^/6-) 但前缀转换返回错误的答案 (- *1/+23^456) 而不是 -/*1+23^456。谁能帮忙？

4

1 回答 1

1

实际上，这两个答案都是正确的，因为如果乘法在中缀中排在第一位，您可以切换除法和乘法的顺序。因此，在这种情况下，您的错误答案是正确的。但是，存在从左到右的优先级，因此您的层次结构处理不正确： change else if(x=='*'||x=='/') return 2;。

于 2016-09-08T15:29:45.027 回答