Segmentation fault occuring in evaluation of postfix expression using stack

Question

Here is the full implementation of infix to postfix conversion and evaluation of postfic expression. The the "infix to postfix conversion " is working successfully but the "evaluation " gives a seg fault.

The code is :

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

On debugging this I get :

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.

The problem is here :

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

of evaluation() function.

Again I used the stack implementation explicitly so that I can see where actually the problem lies.

In pop function, the seg. fault is coming at : output=temp->data;

Answer 1

You have 2 problems in your code:

• you pass the original expression to the evaluate function when you should pass postfix:
• you never populate the stack with numeric arguments!

The loop content in evaluate should be (more or less):

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

That is enough to get rid of the seg fault in that simple case. But your algorithm is currently not able to process numbers with more than 1 digit...

Answer 2

The problem is in your pop method. You need to check for head == nullptr. Like:

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

If your evaluatefunction takes the false-path in the first or second loop, you'll dereference a nullptr and get a seg fault.

Like this:

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