String Evaluation

Working code:

Code assumes that given expression will be valid and there is single digit char only to evaluate.

 

 // Evaluating a string  
 bool isOperator(char op){  
      return ( (op=='+')||( op=='-')||(op=='*')||(op=='/'));  
 }  
 int preference(char op1,char op2){  
      if(op1=='(') return -1;  
      else if(op2=='(') return 1;  
      if(op1=='+' || op1=='-'){  
           if(op2=='+'||op2=='-')  
                return 0;  
           else  
                return -1;  
      }  
      else  
           if(op2=='+'||op2=='-')  
                return 1;  
           else  
                return 0;  
 }  
 int applyOperator(int first,char op,int second)  
 {  
      int f = first;  
      int s = second;  
      switch(op){  
           case '+':  
                return f+s;  
                break;  
           case '-':  
                return f-s;  
                break;  
           case '*':  
                return f*s;  
                break;  
           case '/':  
                return f/s;  
      }  
 }  
 int evaluatePostFix(string s){  
      stack<int> st;  
      for(int i=0;i<s.length();i++){  
           if(s[i]>='0' && s[i]<='9')  
                st.push(s[i]-'0');  
           else{  
                int a = st.top();  
                st.pop();  
                int b = st.top();  
                st.pop();   
                int ans = applyOperator(b,s[i],a);  
                //cout<<ans<<" ";  
                st.push(ans);  
           }       
      }  
      return st.top();  
 }  
 string infixToPostfixConversion(string s)  
 {  
      string postfix = ""; // Final postfix conversion of given string  
      stack<char> st;  
      for(int i=0;i<s.length();i++){  
           // If digit is 0 to 9 then directly print it to output  
           if(s[i]>='0' && s[i]<='9'){  
                postfix.push_back(s[i]);  
           }  
           else   
                if(isOperator(s[i])){  
                     if(st.empty())  
                          st.push(s[i]);  
                     else  
                          if( preference(st.top(),s[i])<0)  
                               st.push(s[i]);  
                          else  
                               if(preference(st.top(),s[i])==0){  
                                    postfix.push_back(st.top());  
                                    st.pop();  
                                    st.push(s[i]);  
                               }  
                               else{  
                                    while(!st.empty() && preference(st.top(),s[i])>0){  
                                         //cout<<"in";  
                                         postfix.push_back(st.top());  
                                         st.pop();  
                                    }  
                                    st.push(s[i]);  
                               }  
                }  
                else{  
                     if(s[i]=='(')  
                          st.push('(');  
                     else{  
                          //cout<<s[i]<<" "<<st.size()<<endl;  
                          while(!st.empty() && st.top()!='('){  
                               //cout<<st.top()<<" ";  
                               postfix.push_back(st.top());  
                               st.pop();  
                          }  
                          st.pop();  
                     }            
                }  
      }  
      while(! st.empty())  
      {  
           postfix.push_back(st.top());  
           st.pop();  
      }  
      //cout<<postfix<<endl;  
      return postfix;  
 }  
 int eval(string s){  
      string s1 = infixToPostfixConversion(s);  
      cout<<"Converted String is "<<s1<<endl;  
      return evaluatePostFix(s1);  
 }  
 int main()  
 {  
      cout<<eval("5*(2+(3*4*5)+5/6)")<<endl;;  
      cout<<eval("1+2+3*(4+5)*9+4-5*2");  
      return 0;  
 }  

Evaluation of a string

We can convert the given string to postfix string and then evaluate it.

Consider example for conversion of infix string to postfix string

A * (B + C * D) + E becomes A B C D * + * E +

	current symbol	operator stack	postfix string
1	A		A
2	*	*	A
3	(	* (	A
4	B	* (	A B
5	+	* ( +	A B
6	C	* ( +	A B C
7	*	* ( + *	A B C
8	D	* ( + *	A B C D
9	)	*	A B C D * +
10	+	+	A B C D * + *
11	E	+	A B C D * + * E
12			A B C D * + * E +

A summary of the rules follows:
1. Print operands as they arrive.
2. If the stack is empty or contains a left parenthesis on top, push the incoming operator onto the stack.
3. If the incoming symbol is a left parenthesis, push it on the stack.
4. If the incoming symbol is a right parenthesis, pop the stack and print the operators until you see a left parenthesis. Discard the pair of parentheses.
5. If the incoming symbol has higher precedence than the top of the stack, push it on the stack.
6. If the incoming symbol has equal precedence with the top of the stack, use association. If the association is left to right, pop and print the top of the stack and then push the incoming operator. If the association is right to left, push the incoming operator.
7. If the incoming symbol has lower precedence than the symbol on the top of the stack, pop the stack and print the top operator. Then test the incoming operator against the new top of stack.
8. At the end of the expression, pop and print all operators on the stack. (No parentheses should remain.)


Evaluation of postfix string:

1. For each token  
2. {  
3.     If (token is a number)  
4.     {  
5.         Push value onto stack  
6.     }  
7.   
8.     If (token is an operator)  
9.     {  
10.         Pop 2 top values from the stack  
11.         Evaluate operator using popped values as args  
12.         Push result onto stack  
13.     }  
14. }  

Getting segmentation fault due to array size limit. Try this !

 Use static keyword:

Code:

static int i[2000][2000]; 

Without doing it, it goes to the heap, which is limited in size by the linker (can be something like 1 megabyte) and is not suitable for storing large variables.

Be aware that your function is no more reentrant after that.

or

Assign Dynamic allocation to array:
 

Code:

int **array=malloc(2000*2000*sizeof(int));

or something similar. or use the fancy "new" keyword in C++.

(for those who say malloc is not C++ enough, that may be true, but it's still functional)

Quick Sort With custom comparator function

Function Prototype:

void qsort (void* base, size_t num, size_t size,
            int (*comparator)(const void*,const void*));


The comparator function takes two pointers as arguments (both type-casted to const void*) and defines the order of the elements by returning (in a stable and transitive manner


int comparator(const void* p1, const void* p2);
Return value meaning
<0 The element pointed by p1 goes before the element pointed by p2
0  The element pointed by p1 is equivalent to the element pointed by p2
>0 The element pointed by p1 goes after the element pointed by p2.

Example:

Suppose we have to sort a given array with order defined by another array.
Given two arrays A1[] and A2[], sort A1 in such a way that the relative order among the elements will be same as those are in A2. For the elements not present in A2, append them at last in sorted order.  

 #include "iostream"   
 #include "bits/stdc++.h"  
 using namespace std;  
 
 int order[100]={2,1,8,3,4};  
 int size_orderArray;  

 int searchInOrderArray(int key){  
  for(int i=0;i<size_orderArray;i++)  
   if(order[i]==key) return i;  
  return -1;  
 }
  
 int comparator(const void* a, const void *b){  
  int index1 = searchInOrderArray(*(const int*)a);  
  int index2 = searchInOrderArray(*(const int*)b);  
  //cout<<index1<<" "<<index2<<endl;  
  if(index1!=-1 && index2!=-1)  
   return index1-index2;  
  if(index1!=-1 && index2==-1)  
   return -1;  
  if(index2!=-1 && index1==-1)  
   return 1;  
  return *(const int*)a-*(const int*)b;  
 }  

 void sortArrayByAnotherArray(int *arr,int n1){  
  qsort((void*) arr,n1,sizeof(int),comparator);  
 }  

 int main()  
 {  
   int ar1[] = {2, 1, 2, 5, 7, 1, 9, 3, 6, 8, 8, 7, 5, 6, 9, 7, 5};  
   int m = sizeof(ar1)/sizeof(ar1[0]);  
   size_orderArray = 5;  
   sortArrayByAnotherArray(ar1,m);  
   for(int i=0;i<m;i++)  
    cout<<ar1[i]<<" ";  
 }  
 

Another Example:
Given an array of words, print all anagrams together. For example, if the given array is {“cat”, “dog”, “tac”, “god”, “act”}, then output may be “cat tac act dog god”

 int comparatorForAnagram(const void* a,const void *b)  
 {  
  string s1 = *(const string*)a;  
  string s2 = *(const string*)b;  
  sort(s1.begin(),s1.end());  
  sort(s2.begin(),s2.end());  
  if(s1==s2)  
   return 0;  
  else  
   if(s1.compare(s2)>0)  
    return 1;  
   else  
    return -1;   
 }  
 void sortAccordingToAnagram(string *words,int n)  
 {  
  qsort((void*)words,n,sizeof(string),comparatorForAnagram);  
  for(int i=0;i<n;i++)  
   cout<<words[i]<<" ";  
 }