Errore di segmentazione che si verifica nella valutazione dell'espressione postfissa utilizzando lo stack

Question

Di seguito è riportata l'implementazione completa di conversione da infisso a postfissa e valutazione dell'espressione postfatica. La "conversione da infisso a postfisso" funziona correttamente ma la "valutazione" dà un errore di seg.

Il codice è:

#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; 
} 

il debug questo ottengo:

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. 

Il problema è qui:

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

di valutazione della funzione().

Ancora una volta ho utilizzato l'implementazione dello stack in modo esplicito in modo da poter vedere dove si trova effettivamente il problema.

Nella funzione pop, il seg. errore è in arrivo: output=temp->data;

Answer 1

Hai 2 problemi nel codice:

• si passa l'originale expression alla funzione evaluate quando si dovrebbe passare postfix:
• mai popolano la impilare con argomenti numerici!

Il contenuto loop nella valutazione dovrebbe essere (più o meno):

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 
     ... 

Questo è sufficiente per sbarazzarsi del guasto seg in questo caso semplice. Ma il tuo algoritmo non è attualmente in grado di elaborare numeri con più di 1 cifra ...

Answer 2

Il problema è nel metodo pop. È necessario verificare per head == nullptr. Come:

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;  
} 

Se la vostra funzione evaluate prende il falso-percorso nel primo o nel secondo ciclo, avrete dereference un nullptr e ottenere un guasto seg.

Ti piace questa:

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