Segmentierungsfehler bei der Auswertung von Postfix-Ausdruck mit Stack

Question

Hier ist die vollständige Implementierung von Infix zu Postfix-Konvertierung und Auswertung von postfic Ausdruck. Die "Infix zu Postfix Konvertierung" funktioniert erfolgreich, aber die "Auswertung" gibt einen Seg Fehler.

Der Code ist:

#include<iostream> 
//#include<stack> 
#include<string> 
#include<cmath> 

using namespace std; 

template<class T1> 
struct node 
{ 

    T1 data; 
    node<T1> *next; 

}; 
template<class T1> 
class stack 
{ 
    node<T1> *head; 
    public: 
     stack() 
     { 
      head=NULL; 
     } 
     void push(T1); 
     int empty() 
      { 
       if(head==NULL) 
       return 1; 
       return 0; 
      } 
     T1 top() 
      { 
       T1 temp; 
       temp=head->data; 
       return (temp); 
      } 
     T1 pop(); 
     void show(); 

}; 
template<class T1> 
void stack<T1>::push(T1 input) 
{ 
    node<T1> *ptr; 
    ptr=new node<T1>; 
    ptr->data=input; 
    ptr->next=NULL; 
    if(head!=NULL) 
    { 
     ptr->next=head; 
    } 
    head=ptr; 
} 
template<class T1> 
T1 stack<T1>::pop() 
{ 
    node<T1> *temp; 
    T1 output; 
    temp=head; 
    output=temp->data; 
    head=head->next; 
    delete temp; 
    return output; 

} 
template<class T1> 
void stack<T1>::show() 
{ 
     node<T1> *temp; 
    temp=head; 
    while(temp!=NULL) 
    { 
     cout<<temp->data; 
     temp=temp->next;  
    } 
} 

void evaluate(string postfix) 
{ 
    stack<float>s; 
    float a; 
    int i; 
    for(i=0; i < postfix.length(); i++) 
    { 
    if(isalpha(postfix[i])) 
    { 
    cout<<"enter the value of\t"; 
    cout<<postfix[i]; 
    cin>>a; 
    s.push(a); 
    } 
    else 
    { 
     float x,y; 
     y=s.pop(); //s.pop(); 
     x=s.pop(); //s.pop(); 

     char token=postfix[i]; 
     if(token=='+') 
     { 

     x=x+y; 
     s.push(x); 
     } 
     if(token=='-') 
     { 

     x=x-y; 
     s.push(x); 
     } 
     if(token=='*') 
     { 

     x=x*y; 
     s.push(x); 
     } 
     if(token=='/') 
     { 

     x=x/y; 
     s.push(x); 
     } 
     if(token=='^') 
     { 

     x=pow(x,y); 
     s.push(x); 
     } 

    } 
    } 
    cout<<"\t Evaluated result is \t"; 
    cout<<s.top(); 
    s.pop(); 
} 

// Function to convert Infix expression to postfix 
string InfixToPostfix(string expression); 

// Function to verify whether an operator has higher precedence over other 
int HasHigherPrecedence(char operator1, char operator2); 

// Function to verify whether a character is operator symbol or not. 
bool IsOperator(char C); 

// Function to verify whether a character is alphanumeric chanaracter (letter or numeric digit) or not. 
bool IsOperand(char C); 

int main() 
{ 
    string expression; 
    cout<<"Enter Infix Expression \n"; 
    getline(cin,expression); 
    string postfix = InfixToPostfix(expression); 
    cout<<"Postfix is : = "<<postfix<<"\n"; 
    evaluate(expression); 
} 

// Function to evaluate Postfix expression and return output 
string InfixToPostfix(string expression) 
{ 
    // Declaring a Stack from Standard template library in C++. 
    stack<char> S; 
    string postfix = ""; // Initialize postfix as empty string. 
    for(int i = 0;i< expression.length();i++) { 

    // Scanning each character from left. 
    // If character is a delimitter, move on. 
    if(expression[i] == ' ' || expression[i] == ',') continue; 

    // If character is operator, pop two elements from stack, perform operation and push the result back. 
    else if(IsOperator(expression[i])) 
    { 
     while(!S.empty() && S.top() != '(' && HasHigherPrecedence(S.top(),expression[i])) 
     { 
     postfix+= S.top(); 
     S.pop(); 
     } 
     S.push(expression[i]); 
    } 
    // Else if character is an operand 
    else if(IsOperand(expression[i])) 
    { 
     postfix +=expression[i]; 
    } 

    else if (expression[i] == '(') 
    { 
     S.push(expression[i]); 
    } 

    else if(expression[i] == ')') 
    { 
     while(!S.empty() && S.top() != '(') { 
     postfix += S.top(); 
     S.pop(); 
     } 
     S.pop(); 
    } 
    } 

    while(!S.empty()) { 
    postfix += S.top(); 
    S.pop(); 
    } 

    return postfix; 
} 

// Function to verify whether a character is english letter or numeric digit. 
// We are assuming in this solution that operand will be a single character 
bool IsOperand(char C) 
{ 
    if(C >= '0' && C <= '9') return true; 
    if(C >= 'a' && C <= 'z') return true; 
    if(C >= 'A' && C <= 'Z') return true; 
    return false; 
} 

// Function to verify whether a character is operator symbol or not. 
bool IsOperator(char C) 
{ 
    if(C == '+' || C == '-' || C == '*' || C == '/' || C== '^') 
    return true; 

    return false; 
} 

// Function to verify whether an operator is right associative or not. 
int IsRightAssociative(char op) 
{ 
    if(op == '^') return true; 
    return false; 
} 

// Function to get weight of an operator. An operator with higher weight will have higher precedence. 
int GetOperatorWeight(char op) 
{ 
    int weight = -1; 
    switch(op) 
    { 
    case '+': 
    case '-': 
    weight = 1; 
    break; 
    case '*': 
    case '/': 
    weight = 2; 
    break; 
    case '^': 
    weight = 3; 
    break; 
    } 
    return weight; 
} 

// Function to perform an operation and return output. 
int HasHigherPrecedence(char op1, char op2) 
{ 
    int op1Weight = GetOperatorWeight(op1); 
    int op2Weight = GetOperatorWeight(op2); 

    // If operators have equal precedence, return true if they are left associative. 
    // return false, if right associative. 
    // if operator is left-associative, left one should be given priority. 
    if(op1Weight == op2Weight) 
    { 
    if(IsRightAssociative(op1)) return false; 
    else return true; 
    } 
    return op1Weight > op2Weight ? true: false; 
} 

Auf diese Debuggen erhalte ich:

Enter Infix Expression 
(5^2)+5 

Breakpoint 1, main() at stack.cpp:155 
warning: Source file is more recent than executable. 
155 string postfix = InfixToPostfix(expression); 
Missing separate debuginfos, use: dnf debuginfo-install libgcc-5.3.1-2.fc23.x86_64 libstdc++-5.3.1-2.fc23.x86_64 
(gdb) n 
156 cout<<"Postfix is : = "<<postfix<<"\n"; 
(gdb) n 
Postfix is : = 52^5+ 
157 evaluate(expression); 
(gdb) s 
evaluate (postfix="(5^2)+5") at stack.cpp:81 
81 stack<float>s; 
(gdb) s 
stack<float>::stack (this=0x7fffffffddd0) at stack.cpp:23 
23    head=NULL; 
(gdb) s 
24   } 
(gdb) s 
evaluate (postfix="(5^2)+5") at stack.cpp:84 
84 for(i=0; i < postfix.length(); i++) 
(gdb) s 
86 if(isalpha(postfix[i])) 
(gdb) s 
96  y=s.pop(); //s.pop(); 
(gdb) s 
stack<float>::pop (this=0x7fffffffddd0) at stack.cpp:60 
60  temp=head; 
(gdb) s 
61  output=temp->data; 
(gdb) s 

Program received signal SIGSEGV, Segmentation fault. 
0x0000000000401a05 in stack<float>::pop (this=0x7fffffffddd0) at stack.cpp:61 
61  output=temp->data; 
(gdb) s 
s 
Program terminated with signal SIGSEGV, Segmentation fault. 
The program no longer exists. 

Das Problem ist hier:

float x,y; 
     y=s.pop(); //s.pop(); 
     x=s.pop(); //s.pop(); 

der Bewertung() Funktion.

Wieder habe ich die Stack-Implementierung explizit benutzt, damit ich sehen kann, wo eigentlich das Problem liegt.

In Pop-Funktion, die seg. Fehler kommt bei: output=temp->data;

Answer 1

Sie haben zwei Probleme im Code:

• Sie das Original expression an die evaluate Funktion übergeben, wenn Sie postfix passieren sollte:
• Sie nie bevölkern die Stapel mit numerischen Argumenten!

Das Loop-Gehalt sollte bewerten (mehr oder weniger):

if(isalpha(postfix[i])) 
    { 
    cout<<"enter the value of\t"; 
    cout<<postfix[i]; 
    cin>>a; 
    s.push(a); 
    } 
    else if (isdigit(postfix[i])) { // do not forget to populate stack! 
     s.push(0.f + postfix[i] - '0'); // raw conversion of digit to float 
    } 
    else 
     ... 

Das reicht in diesem einfachen Fall des seg Fehlers loszuwerden. Aber Ihr Algorithmus ist derzeit nicht in der Lage, Zahlen mit mehr als 1 Ziffer zu verarbeiten ...

Answer 2

Das Problem ist in Ihrer pop Methode. Sie müssen nach head == nullptr suchen. Wie:

template<class T1> 
T1 stack<T1>::pop() 
{ 
    node<T1> *temp; 
    T1 output; 
    if (head == nullptr) 
    { 
     // Error handling.... Perhaps: 
     throw ....; 
    } 
    temp=head; 
    output=temp->data; 
    head=head->next; 
    delete temp; 
    return output;  
} 

Wenn Ihr evaluate Funktion den falschen Pfad in der ersten oder zweiten Schleife dauert, werden Sie dereferenzieren ein nullptr und einen Segmentation Fehler.

So:

void evaluate(string postfix) 
{ 
    stack<float> s; // s is empty and head is nullptr 
    float a; 
    int i; 
    for(i=0; i < postfix.length(); i++) 
    { 
     if(isalpha(postfix[i])) // Assume this evalutes to false in first loop 
     { 
      cout<<"enter the value of\t"; 
      cout<<postfix[i]; 
      cin>>a; 
      s.push(a); 
     } 
     else 
     { 
      float x,y; 
      y=s.pop(); // then you pop from empty stack and dereference a nullptr