Преобразование инфикса в постфикс с использованием стеков (связанных списков) в C++

Всем добрый день! Я новичок в C++ (а также в stackoverflow), и мне нужна помощь ваших экспертов. Что-то не так с этим кодом, даже если нет ошибки или предупреждения. Он просто зависает всякий раз, когда программа выполняется.

Программа конвертирует инфиксы в постфиксы с помощью связанных списков (стеков).

# include <iostream>
# include <cstring>

 using namespace std;

 struct node {
    char data;
    node *next;
 };

 node *top=NULL;
 node *bottom=NULL;
 node *entry;
 node *last_entry;
 node *second_last_entry;

 void push(const char Symbol) {
    entry=new node;
    if(bottom==NULL) {
         entry->data=Symbol;
         entry->next=NULL;
         bottom=entry;
         top=entry;
    }
    else {
         entry->data=Symbol;
         entry->next=NULL;
         top->next=entry;
         top=entry;
    }
}

const char pop( ) {
    char Symbol=NULL;

    if(bottom==NULL)
        cout<<"\n\n\n\t ***  Error : Stack is empty. \n"<<endl;

    else {
        for (last_entry=bottom; last_entry->next!=NULL; last_entry=last_entry->next)
            second_last_entry=last_entry;

        if(top==bottom)
        bottom=NULL;

        Symbol=top->data;

        delete top;

        top=second_last_entry;
        top->next=NULL;
    }

    return Symbol;
}

void infix_to_postfix(const char *Infix) {
    char Infix_expression[100]={NULL};
    char Postfix_expression[100]={NULL};

    strcpy(Infix_expression,"(");
    strcat(Infix_expression,Infix);
    strcat(Infix_expression,")");

    char Symbol[5]={NULL};
    char Temp[5]={NULL};

    for(int count=0;count<strlen(Infix_expression);count++) {
        Symbol[0]=Infix_expression[count];

        if(Symbol[0]=='(')
            push(Symbol[0]);

        else if(Symbol[0]==')') {
           Symbol[0]=pop( );

           while(Symbol[0]!='(')
              {
             strcat(Postfix_expression,Symbol);

             Symbol[0]=pop( );
              }
        }

         else if(Symbol[0]=='^' || Symbol[0]=='*' || Symbol[0]=='/'
                    || Symbol[0]=='+' || Symbol[0]=='-')
        {
           if(Symbol[0]=='*' || Symbol[0]=='/')
              {
             Temp[0]=pop( );

             while(Temp[0]=='^' || Temp[0]=='*' || Temp[0]=='/')
                {
                   strcat(Postfix_expression,Temp);

                   Temp[0]=pop( );
                }

             push(Temp[0]);
              }

           else if(Symbol[0]=='+' || Symbol[0]=='-')
              {
             Temp[0]=pop( );

             while(Temp[0]!='(')
                {
                   strcat(Postfix_expression,Temp);

                   Temp[0]=pop( );
                }

             push(Temp[0]);
              }

           push(Symbol[0]);
        }

         else
        strcat(Postfix_expression,Symbol);
      }

       cout<<"\n\n Postfix Expression : "<<Postfix_expression;
}

 int main( ) {
    char Infix_expression[100]={NULL};
    cout<<"\n\n Enter the Infix Expression : ";
    cin>>Infix_expression;
    infix_to_postfix(Infix_expression);
    return 0;
}

Помогите мне, пожалуйста! Я новичок и без вас далеко не уйду. Большое спасибо!


c++ stack linked-list infix-notation postfix-notation
person First Lady    schedule 18.03.2012    source источник
comment
Вы знаете, как запустить код в отладчике?   -  person J.N.    schedule 18.03.2012
comment
Я не боюсь. Кстати, я использую кодовые блоки.   -  person First Lady    schedule 18.03.2012
comment
Я думаю, вам нужно научиться отлаживать, прежде чем решать эту проблему.   -  person J.N.    schedule 18.03.2012
comment
Ваш код кажется довольно странным (по крайней мере, он может выиграть от нескольких вспомогательных методов и реструктуризации). Я полагаю, вы читали статью о сортировочной станции на вики?   -  person Voo    schedule 18.03.2012

Ответы (2)


arrow_upward
1
arrow_downward

Я думаю, вам нужна помощь, чтобы научиться отлаживать код с помощью этой IDE. Первое, что вы можете попробовать, это добавить больше печати (через cout), чтобы немного яснее увидеть, что происходит, и найти, где программа зависает (или не застряла ли она в бесконечном цикле).

Вот учебник, показывающий, как отлаживать кодовые блоки. К сожалению, я понятия не имею, будет ли это соответствовать вашей конфигурации.

person J.N.    schedule 18.03.2012
comment
Спасибо, J.N.! Но кодовые блоки, которые я использую, были только что загружены бесплатно, и я не могу получить доступ к параметрам сборки для отладки кода. - person First Lady; 18.03.2012
comment
@FirstLady Вам действительно следует использовать IDE, которая позволяет выполнять отладку. Но, глядя на вики-страницу для кодовых блоков ... она выпущена под GPL, поэтому я не очень понимаю вашу точку зрения. Во всяком случае, есть также eclipse CDT (отлично работает для * nix, windows, без понятия Mac) и VS Express для Windows. - person Voo; 18.03.2012
comment
Спасибо, Воу! Я поищу eclipse CDT. Спасибо! :) - person First Lady; 18.03.2012

arrow_upward
1
arrow_downward

Для стека вам нужен только один указатель стека.

void push(const char Symbol) {
    entry = new node;
    entry->data = Symbol;
    entry->next = top;
    top = entry;
}


const char pop( ) {
    if (!top) {
        cout << "\n\n\n\t ***  Error : Stack is empty. \n" << endl;
        return ' ';
    }
    node* entry = top;
    top = top->next;
    char ch = entry->data;
    delete entry;
    return ch;
}

const bool is_empty() {
    return !top;
}

Это должно устранить некоторые ошибки, но, вероятно, не все. Иногда я видел то же самое с двумя стеками: один для операторов, другой для операндов. Я не обязательно советую это. Лучше начать с нуля и сохранить алгоритм простым и абстрактным, возможно, сначала в псевдокоде.

person Joop Eggen    schedule 18.03.2012
comment
Эй, теперь это работает! Большое спасибо, Юп Эгген! Больше благословений! Спасибо большое! - person First Lady; 18.03.2012