Преобразование инфикса в постфикс с использованием структуры данных стека со связанным списком - PullRequest
Новая
       55

Преобразование инфикса в постфикс с использованием структуры данных стека со связанным списком

1 голос
/ 19 июня 2020

Я пытаюсь создать программу для преобразования инфиксного выражения в постфиксное выражение с использованием структуры данных стека в C ++ с использованием структуры Node. Связанные функции предназначены для pu sh, извлечения значений из стека. Программа компилируется, но после того, как я ввожу пример инфиксного выражения 'a + b' в окно вывода, возникает ошибка времени выполнения. Вот полный код .. 

#include <iostream>
#include<cstring>

using namespace std;

struct Node{
    char data;
    struct Node * next;
}*top=NULL;

void Push(char x)
{   struct Node* p=new Node;
    if(p==NULL)
        cout<<"\nStack Overflow";
    else{
        p->data=x;
        p->next=top;
        top=p;
    }
}  

char Pop(){
    int x=-1;
    struct Node * p;
    if(top==NULL)
        cout<<"\nStack is Empty";
    else{
         p=top;
         x=p->data;
         top = top->next;
         delete p;
    }
    return x;
}

int isEmpty(){
    return top?0:1;
}

int Pre(char ch){
    if(top==NULL)
        return 0;
    else if(ch == '-' || ch == '+')
        return 1;
    else if(ch == '*' || ch == '/')
        return 2;
    else
        return 3;
}
char * InToPost(char *infix){
    char *postfix = new char[strlen(infix)+1];
    int i=0,j=0;
    while(infix[i]!='\0')
    {
        if(Pre(infix[i]>Pre(top->data)))
            Push(infix[i++]);
        else{
            while(Pre(infix[i])<=Pre(top->data))
                postfix[j++]= Pop();
          }
    }
    while(!isEmpty())
        postfix[j++]=Pop();
    postfix[j] = '\0';
    return postfix;
}

int main(){
    char *infix = new char[30];
    cin>>infix;
   cout<<InToPost(infix);
}

Ответы [ 2 ]

0 голосов
/ 19 июня 2020

Я изменил ваш код.

1) Вместо int x = -1; объявить char x = -1 in -> char Pop ()

2) Измените функцию pre в соответствии с приведенным ниже кодом

int Pre (char ch) {

if(ch == '-' || ch == '+') return 1;

if(ch == '*' || ch == '/') return 2;

else    return 0;

}

3) Изменить while l oop внутри InToPost ()

while (infix [i]! = '\ 0') 

 {

     if(Pre(infix[i])==0)   // if char is operand then push into postfix array

         postfix[j++] = infix[i++];   // you were not using j++ with postfix array

     else{

        if(isEmpty()==1)  // if stack is empty then push into Stack

            Push(infix[i++]);
        else
        {
            if(Pre(infix[i])>=Pre(top->data))  // If coming operator has same or less predence then push into Stack
                Push(infix[i++]);
            else{
                while(Pre(infix[i])<=Pre(top->data))
                   postfix[j++]= Pop();
            }
         }

       }
 }
0 голосов
/ 19 июня 2020

Причиной ошибки может быть то, что вы не увеличили значение 'i' в другой части while l oop. Это то, что приводит к бесконечному l oop. Кроме того, вы могли ошибочно поместить круглую скобку в условие if для while l oop. Но даже если вы внесете эти изменения, это не даст вам правильных результатов. Я думаю, вы ошибаетесь. Каждый алфавит следует помещать непосредственно в массив postfix, а не в стек. Мы должны проверять приоритеты только операторов, а не алфавитов. Вы можете попробовать реализовать следующий код. Я не использовал связанную реализацию стека, но напрямую использовал стек из STL, но вы можете внести необходимые изменения в соответствии с вашими потребностями. Здесь я вставил дополнительный символ A в стек, чтобы проверить, есть ли в стеке В нем нет операторов. 

int prec(char ch){
    if(ch == '^')
        return 3;
    if(ch == '*' or ch == '/')
        return 2;
    if(ch == '+' or ch == '-')
        return 1;
    return -1;
}

string infixToPostfix(string x)
{
    stack<char> s;
    s.push('A');
    string ans;
    int n = x.length();

    for(int i = 0 ; i < n; i++){

        if((x[i] >= 'a' and x[i] <= 'z') or (x[i] >= 'A' and x[i] <= 'Z'))
            ans += x[i];

        else if(x[i] == '(')
            s.push(x[i]);

        else if(x[i] == ')'){

            while(s.top() != 'A' and s.top() != '('){
                ans += s.top();
                s.pop();
            }
            if(s.top() == '('){
                s.pop();
            }
        }
        else{

            while(s.top() != 'A' and prec(x[i]) <= prec(s.top())){
                ans += s.top();
                s.pop();
            }
            s.push(x[i]);

        }

    }

    while(s.top() != 'A'){
        ans += s.top();
        s.pop();
    }

    return ans;
}

Попробуйте это. Он должен работать! Он также будет работать для выражений, содержащих парантез, например a + b * (c + d) + (f + g)

...