Here is the full implementation of infix for postfix conversion and evaluation of postfix expression. The postfix conversion infix works successfully, but the evaluation gives a seg error.
Code:
#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=xy; 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; }
When debugging, 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();
evaluation functions ().
Again, I used the stack implementation explicitly so that I can see where the problem is actually.
In a pop function segment. The error occurs when: output=temp->data;
source share