Arithmetic expression evaluation program in C++

In this tutorial, we will learn the program for arithmetic expression evaluation in C++ with some cool and easy examples. In many situations, you might have to come up with this type of requirement.

I know you are here just because you need this program in C++.

If you don’t know the program for arithmetic expression evaluation then you are at the right place. Because, in this tutorial, we going to learn the program for arithmetic expression evaluation.

Arithmetic expression evaluation in C++

Firstly, For evaluating arithmetic expressions the stack organization is preferred and also effective.

Additionally, here we come across a keyword Infix notation. Expressions that are represented in this each operator is written between two operands (i.e., x + y).

From the above notation, one should distinguish between (x + y)*z and x + (y * z) by using some operator-precedence convention or parentheses. Hence, the sequence of operands and operators in an arithmetic expression does not find the order where these operations are to be performed.

 

  1. Prefix notation
    If the operator is placed before its operands then it is said to be a prefix notation. Here no parentheses are required, i.e.,
+xy
  1. Postfix notation
    If the operator is placed after its operands then it is said to be a postfix notation. Here also no parentheses are required, i.e.
xy+

Note; Prefix notation also called polish notation.
Reverse polish notation is postfix notation.

Infix notation is the traditional notation, so for stack organized computers, postfix notation is best-suited notation. Hence, we have to convert them both. This conversion is considered as the operational hierarchy.

We have different precedence levels for 5 binary operators:

  • Lowest: Addition (+) and Subtraction (-)
  • Highest: Exponentiation (^)
  • Next highest: Division(/)  and Multiplication(*).

For example –

Infix : (x-y)*[z/(p+q)+r]

Post-fix : xy- zpq +/r +*.

 

Then, inside parentheses (x-y) and (p+q) we perform the arithmetic. The z/(p+q) division has to be done prior to the addition of r. Then the two terms inside the bracket and parentheses are multiplied.

Now by using stack we have to solve out the values.

The approach for the result are:

  1. Expression must be converted into postfix notation.
  2. Operands must be pushed into the stack in the order they appear.
  3. Pop two topmost operands when any operator encounters for executing the operation.
  4. We must push them inside the stack.
  5. After these steps, the topmost element of the stack is our result.

Example –

Infix: (1+2) * (3+4)

Post-fix: 1 2 + 3 4 + *

Result; 21

Stack operations

C++ program for arithmetic expression evaluation

program for evaluation in C++

Example; for converting infix notation to postfix notation

#include<bits/stdc++.h> 
using namespace std; 

int pre(char ch) 
{ 
  if(ch == '^') 
  return 3; 
  else if(ch == '*' || ch == '/') 
  return 2; 
  else if(ch == '+' || ch == '-') 
  return 1; 
  else
  return -1; 
} 

void infixToPostfix(string s) 
{ 
  std::stack<char> st; 
  st.push('N'); 
  int l = s.length(); 
  string ns; 
  for(int i = 0; i < l; i++) 
  { 
     
    if((s[i] >= 'a' && s[i] <= 'z')||(s[i] >= 'A' && s[i] <= 'Z')) 
    ns+=s[i]; 

      else if(s[i] == '(') 
    
    st.push('('); 
  
    else if(s[i] == ')') 
    { 
      while(st.top() != 'N' && st.top() != '(') 
      { 
        char ch = st.top(); 
        st.pop(); 
      ns += ch; 
      } 
      if(st.top() == '(') 
      { 
        char ch = st.top(); 
        st.pop(); 
      } 
    } 
    
    else{ 
      while(st.top() != 'N' && pre(s[i]) <= pre(st.top())) 
      { 
        char ch = st.top(); 
        st.pop(); 
        ns += ch; 
      } 
      st.push(s[i]); 
    } 

  } 

  while(st.top() != 'N') 
  { 
    char ch = st.top(); 
    st.pop(); 
    ns += ch; 
  } 
  
  cout << ns << endl; 

} 

int main() 
{ 
  string sol = "a+b*(c^d-e)^(f+g*h)-i"; 
  infixToPostfix(sol); 
  return 0; 
} 

 

output:
abcd^e-fgh*+^*+i-

Example; for evaluating postfix expression

#include <iostream> 
#include <string.h> 

using namespace std; 

struct Stack 
{ 
  int first; 
  unsigned cap; 
  int* array; 
}; 

struct Stack* stackCreate( unsigned cap ) 
{ 
  struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack)); 

  if ( !stack ) return null;
  stack -> first=-1; 
  stack -> cap=cap; 
  stack -> array = (int*) malloc(stack->cap * sizeof(int)); 

//go

  if ( !stack -> array) return null; 
  return stack; 
} 

int empty ( struct Stack* stack ) 
{   return stack -> first==-1 ;}
char peek (struct Stack* stack) 
{   return stack -> array[stack -> first];} 
char pop(struct Stack* stack) 
{ 
  if (!empty(stack)) 
    return stack -> array[stack -> first--] ; return '$'; 
} 
void push(struct Stack* stack,char ope) 
{  stack->array[++stack->first]=ope;}  
int postfixEvaluate(char*expression) 
{  struct Stack* stack=StackCreate(strlen(expression)); 
  int i;
  if (!stack) return-1;
  for (i = 0; expression[i]; ++i) 
  { 
    if (isdigit(expression[i])) 
      push(stack, expression[i] - '0'); //till here

    else
    { 
      int val1 = pop(stack); 
      int val2 = pop(stack); 
      switch (expression[i]) 
      { 
      case '+': push(stack, val2 + val1); break; 
      case '-': push(stack, val2 - val1); break; 
      case '*': push(stack, val2 * val1); break; 
      case '/': push(stack, val2/val1); break; 
      } 
    } 
  } 
  return pop(stack); 
}  
int main() 
{ 
  char expression[] = "123*+4-"; 
  cout<<"postfix evaluation: "<< postfixEvaluate(expression); 
  return 0; 
} 

 

 

output:
postfix evaluation: 3

Explanation

123*+4-

((3*2)+1)-4

Also read:

Add two numbers without using Arithmetic Operators in C++

Leave a Reply

Your email address will not be published. Required fields are marked *