Evaluation of expression using stack














































Evaluation of expression using stack



<!-- HTML generated using hilite.me --><div style="background: #ffffff; overflow:auto;width:auto;border:solid gray;border-width:.1em .1em .1em .8em;padding:.2em .6em;"><pre style="margin: 0; line-height: 125%"><span style="color: #888888">/* Description : First we make two stacks  one contain operators and one contaion operands.We push operator and operand in the stacks</span>
<span style="color: #888888"> then we check precedence of operator and then pop higher precedence operator and pop two operands and then after finding result we again add result to operand stack if ) bracket will come we complete pop the operator stack while ) bracket will not come and also pop two operand and push result in operand stack */</span>
<span style="color: #557799">#include&lt;iostream&gt;</span>
<span style="color: #888888">//header file for string </span>
<span style="color: #557799">#include&lt;string&gt;</span>
<span style="color: #008800; font-weight: bold">using</span> <span style="color: #008800; font-weight: bold">namespace</span> std;
<span style="color: #557799">#define max 1000</span>
<span style="color: #888888">//template for handle int,float or char in stack</span>
<span style="color: #008800; font-weight: bold">template</span><span style="color: #333333">&lt;</span><span style="color: #008800; font-weight: bold">class</span> <span style="color: #BB0066; font-weight: bold">T</span><span style="color: #333333">&gt;</span>
<span style="color: #888888">//class for stack</span>
<span style="color: #008800; font-weight: bold">class</span> <span style="color: #BB0066; font-weight: bold">stack</span>{
    T a[max];
    <span style="color: #333399; font-weight: bold">int</span> top<span style="color: #333333">=-</span><span style="color: #0000DD; font-weight: bold">1</span>;
    <span style="color: #997700; font-weight: bold">public:</span>
      stack(){top<span style="color: #333333">=-</span><span style="color: #0000DD; font-weight: bold">1</span>;}
       <span style="color: #333399; font-weight: bold">void</span> push(T x);
        <span style="color: #333399; font-weight: bold">void</span> <span style="color: #0066BB; font-weight: bold">pop</span>();
        <span style="color: #333399; font-weight: bold">bool</span> <span style="color: #0066BB; font-weight: bold">empty</span>();
        <span style="color: #333399; font-weight: bold">bool</span> <span style="color: #0066BB; font-weight: bold">full</span>();
        T <span style="color: #0066BB; font-weight: bold">peek</span>();
};
<span style="color: #008800; font-weight: bold">template</span><span style="color: #333333">&lt;</span><span style="color: #008800; font-weight: bold">class</span> <span style="color: #BB0066; font-weight: bold">T</span><span style="color: #333333">&gt;</span>
<span style="color: #888888">//push element in the stack</span>
<span style="color: #333399; font-weight: bold">void</span> stack<span style="color: #333333">&lt;</span>T<span style="color: #333333">&gt;::</span>push(T x)
{
   
     a[<span style="color: #333333">++</span>top]<span style="color: #333333">=</span>x;
}
<span style="color: #888888">//decrese the top by 1</span>
<span style="color: #008800; font-weight: bold">template</span><span style="color: #333333">&lt;</span><span style="color: #008800; font-weight: bold">class</span> <span style="color: #BB0066; font-weight: bold">T</span><span style="color: #333333">&gt;</span>
<span style="color: #333399; font-weight: bold">void</span> stack<span style="color: #333333">&lt;</span>T<span style="color: #333333">&gt;::</span>pop()
{
   <span style="color: #333333">--</span>top;
}
<span style="color: #888888">//check whether stack is empty</span>
<span style="color: #008800; font-weight: bold">template</span><span style="color: #333333">&lt;</span><span style="color: #008800; font-weight: bold">class</span> <span style="color: #BB0066; font-weight: bold">T</span><span style="color: #333333">&gt;</span>
<span style="color: #333399; font-weight: bold">bool</span> stack<span style="color: #333333">&lt;</span>T<span style="color: #333333">&gt;::</span>empty()
{
   <span style="color: #008800; font-weight: bold">return</span> top<span style="color: #333333">==-</span><span style="color: #0000DD; font-weight: bold">1</span>;
}


<span style="color: #008800; font-weight: bold">template</span><span style="color: #333333">&lt;</span><span style="color: #008800; font-weight: bold">class</span> <span style="color: #BB0066; font-weight: bold">T</span><span style="color: #333333">&gt;</span>
<span style="color: #888888">//check whether stack is full or not</span>
<span style="color: #333399; font-weight: bold">bool</span> stack<span style="color: #333333">&lt;</span>T<span style="color: #333333">&gt;::</span>full()
{
   <span style="color: #008800; font-weight: bold">return</span> top<span style="color: #333333">==</span>max<span style="color: #333333">-</span><span style="color: #0000DD; font-weight: bold">1</span>;
}
<span style="color: #008800; font-weight: bold">template</span><span style="color: #333333">&lt;</span><span style="color: #008800; font-weight: bold">class</span> <span style="color: #BB0066; font-weight: bold">T</span><span style="color: #333333">&gt;</span>
<span style="color: #888888">//return value at top of stack</span>
T stack<span style="color: #333333">&lt;</span>T<span style="color: #333333">&gt;::</span>peek()
{
   <span style="color: #008800; font-weight: bold">if</span>(top<span style="color: #333333">!=-</span><span style="color: #0000DD; font-weight: bold">1</span>)
   <span style="color: #008800; font-weight: bold">return</span> a[top];
  <span style="color: #008800; font-weight: bold">else</span>
   <span style="color: #008800; font-weight: bold">return</span> <span style="color: #333333">-</span><span style="color: #0000DD; font-weight: bold">1</span>;
}
<span style="color: #888888">//function to check precedence</span>
<span style="color: #333399; font-weight: bold">int</span> precedence(<span style="color: #333399; font-weight: bold">int</span> op){
    <span style="color: #008800; font-weight: bold">if</span>(op <span style="color: #333333">==</span> <span style="color: #0000DD; font-weight: bold">42</span><span style="color: #333333">||</span>op <span style="color: #333333">==</span> <span style="color: #0000DD; font-weight: bold">47</span>)
    <span style="color: #008800; font-weight: bold">return</span> <span style="color: #0000DD; font-weight: bold">2</span>;
    <span style="color: #008800; font-weight: bold">if</span>(op <span style="color: #333333">==</span> <span style="color: #0000DD; font-weight: bold">43</span><span style="color: #333333">||</span>op <span style="color: #333333">==</span> <span style="color: #0000DD; font-weight: bold">45</span>)
    <span style="color: #008800; font-weight: bold">return</span> <span style="color: #0000DD; font-weight: bold">1</span>;
    <span style="color: #008800; font-weight: bold">return</span> <span style="color: #0000DD; font-weight: bold">0</span>;
}
 
<span style="color: #888888">// Function return value after performing operation </span>
<span style="color: #333399; font-weight: bold">int</span> operate(<span style="color: #333399; font-weight: bold">int</span> a, <span style="color: #333399; font-weight: bold">int</span> b, <span style="color: #333399; font-weight: bold">int</span> op){
    <span style="color: #008800; font-weight: bold">switch</span>(op){
        <span style="color: #008800; font-weight: bold">case</span> <span style="color: #0000DD; font-weight: bold">43</span>: <span style="color: #008800; font-weight: bold">return</span> a <span style="color: #333333">+</span> b;
        <span style="color: #008800; font-weight: bold">case</span> <span style="color: #0000DD; font-weight: bold">45</span>: <span style="color: #008800; font-weight: bold">return</span> a <span style="color: #333333">-</span> b;
        <span style="color: #008800; font-weight: bold">case</span>  <span style="color: #0000DD; font-weight: bold">42</span>: <span style="color: #008800; font-weight: bold">return</span> a <span style="color: #333333">*</span> b;
        <span style="color: #008800; font-weight: bold">case</span> <span style="color: #0000DD; font-weight: bold">47</span>: <span style="color: #008800; font-weight: bold">return</span> a <span style="color: #333333">/</span> b;
    }
}
 
<span style="color: #888888">//function to evaluate the expression</span>
<span style="color: #333399; font-weight: bold">int</span> evaluation(string exp){
    
     
    <span style="color: #888888">// stack to store operands. </span>
    stack <span style="color: #333333">&lt;</span><span style="color: #333399; font-weight: bold">int</span><span style="color: #333333">&gt;</span> opnd;
     
    <span style="color: #888888">// stack to store operators. </span>
    stack <span style="color: #333333">&lt;</span><span style="color: #333399; font-weight: bold">int</span><span style="color: #333333">&gt;</span> optr;
     
    <span style="color: #008800; font-weight: bold">for</span>(<span style="color: #333399; font-weight: bold">int</span> i <span style="color: #333333">=</span> <span style="color: #0000DD; font-weight: bold">0</span>; i <span style="color: #333333">&lt;</span> exp.length(); i<span style="color: #333333">++</span>){
         
      
        
       <span style="color: #888888">// if character is an opening  brace add it to optr stack</span>
      <span style="color: #008800; font-weight: bold">if</span>(exp[i]<span style="color: #333333">==</span><span style="color: #0044DD">&#39; &#39;</span>)
         <span style="color: #008800; font-weight: bold">continue</span>;
       <span style="color: #008800; font-weight: bold">else</span> <span style="color: #0066BB; font-weight: bold">if</span>(exp[i] <span style="color: #333333">==</span> <span style="color: #0000DD; font-weight: bold">62</span>){
            optr.push(exp[i]);
        }
         
        <span style="color: #888888">//if it is a number add it to opnd stack</span>
      
        <span style="color: #008800; font-weight: bold">else</span> <span style="color: #0066BB; font-weight: bold">if</span>(exp[i]<span style="color: #333333">&gt;=</span><span style="color: #0000DD; font-weight: bold">48</span><span style="color: #333333">&amp;&amp;</span>exp[i]<span style="color: #333333">&lt;=</span><span style="color: #0000DD; font-weight: bold">57</span>) {
            <span style="color: #333399; font-weight: bold">int</span> res <span style="color: #333333">=</span> <span style="color: #0000DD; font-weight: bold">0</span>;
             
            <span style="color: #888888">//if number have two or more digit</span>
            <span style="color: #008800; font-weight: bold">while</span>(i <span style="color: #333333">&lt;</span> exp.length() <span style="color: #333333">&amp;&amp;</span> exp[i]<span style="color: #333333">&gt;=</span><span style="color: #0000DD; font-weight: bold">48</span><span style="color: #333333">&amp;&amp;</span>exp[i]<span style="color: #333333">&lt;=</span><span style="color: #0000DD; font-weight: bold">57</span> )
            {
                res <span style="color: #333333">=</span> (res<span style="color: #333333">*</span><span style="color: #0000DD; font-weight: bold">10</span>) <span style="color: #333333">+</span> (exp[i]<span style="color: #333333">-</span><span style="color: #0000DD; font-weight: bold">48</span>);
                i<span style="color: #333333">++</span>;
            }
             
            opnd.push(res);
          
        }
         
        <span style="color: #888888">// if closing bracket comes don&#39;t add it to stack and pop the optr and opnd and perform the operation while optr not empty</span>
      
        <span style="color: #008800; font-weight: bold">else</span> <span style="color: #0066BB; font-weight: bold">if</span>(exp[i] <span style="color: #333333">==</span> <span style="color: #0000DD; font-weight: bold">63</span>)
        {
            <span style="color: #008800; font-weight: bold">while</span>(<span style="color: #333333">!</span>optr.empty() <span style="color: #333333">&amp;&amp;</span> optr.peek() <span style="color: #333333">!=</span> <span style="color: #0000DD; font-weight: bold">62</span>)
            {
                <span style="color: #333399; font-weight: bold">int</span> op2 <span style="color: #333333">=</span> opnd.peek();
                opnd.pop();
                 
                <span style="color: #333399; font-weight: bold">int</span> op1 <span style="color: #333333">=</span> opnd.peek();
                opnd.pop();
                 
                <span style="color: #333399; font-weight: bold">int</span> op <span style="color: #333333">=</span> optr.peek();
                optr.pop();
                 
                opnd.push(operate(op1, op2, op));
            }
             
            <span style="color: #888888">//at last pop opening brace. </span>
            <span style="color: #008800; font-weight: bold">if</span>(<span style="color: #333333">!</span>optr.empty())
               optr.pop();
        }
 
         
        <span style="color: #888888">// Current token is an operator. </span>
        <span style="color: #008800; font-weight: bold">else</span>
        {
            <span style="color: #888888">// if top of optr has same or greater  precedence to current operator</span>
           
           
            <span style="color: #008800; font-weight: bold">while</span>(<span style="color: #333333">!</span>optr.empty() <span style="color: #333333">&amp;&amp;</span> precedence(optr.peek())
                                <span style="color: #333333">&gt;=</span> precedence(exp[i])){
                <span style="color: #333399; font-weight: bold">int</span> op2 <span style="color: #333333">=</span> opnd.peek();
                opnd.pop();
                 
                <span style="color: #333399; font-weight: bold">int</span> op1 <span style="color: #333333">=</span> opnd.peek();
                opnd.pop();
                 
                <span style="color: #333399; font-weight: bold">int</span> op <span style="color: #333333">=</span> optr.peek();
                
                optr.pop();

                 
                opnd.push(operate(op1, op2, op));
               }
           
        
             
            <span style="color: #888888">// Push current operator to optr. </span>
            optr.push(exp[i]);
           
        }
     
    }
  
   
   
     
    <span style="color: #888888">//after all operation </span>
    <span style="color: #008800; font-weight: bold">while</span>(<span style="color: #333333">!</span>optr.empty()){
        <span style="color: #333399; font-weight: bold">int</span> op2 <span style="color: #333333">=</span> opnd.peek();
        opnd.pop();
        
                 
        <span style="color: #333399; font-weight: bold">int</span> op1 <span style="color: #333333">=</span> opnd.peek();
        opnd.pop();
        
                 
        <span style="color: #333399; font-weight: bold">int</span> op <span style="color: #333333">=</span> optr.peek();
        
        optr.pop();
      
            
       opnd.push(operate(op1, op2, op));
    }
     
    <span style="color: #888888">//top of the opnd contain result </span>
    
    
    <span style="color: #008800; font-weight: bold">return</span> opnd.peek();
   
}
<span style="color: #333399; font-weight: bold">int</span> main()
{
  
  string str<span style="color: #333333">=</span><span style="background-color: #fff0f0">&quot;2 * 3 + 8 * 1&quot;</span>;
   string stl<span style="color: #333333">=</span><span style="background-color: #fff0f0">&quot;8 * 9 - 2&quot;</span>;
  
  
   cout<span style="color: #333333">&lt;&lt;</span>evaluation(str)<span style="color: #333333">&lt;&lt;</span>endl;
   cout<span style="color: #333333">&lt;&lt;</span>evaluation(stl)<span style="color: #333333">&lt;&lt;</span>endl;
 
 
   
   
  
   <span style="color: #008800; font-weight: bold">return</span> <span style="color: #0000DD; font-weight: bold">0</span>;
}
<span style="color: #997700; font-weight: bold">output:</span>
<span style="color: #0000DD; font-weight: bold">14</span>
<span style="color: #0000DD; font-weight: bold">70</span>
</pre></div>


Comments