Prefix Expression Evaluation In C++

In this tutorial, we shall learn to evaluate prefix expression in C++. We shall use stack data structure from the STL.
The computer does not know how to evaluate infix expression, which we humans are used to. So it converts the expression either to prefix or to postfix.

Generally, the infix expression is converted to postfix expression by the computer due to its easy and fast implementation. Here we shall input prefix expression and get the evaluated result.

Algorithm and the calculate function

For that, we will scan the string from the rightmost end to the start. If we encounter operands (integer), then we shall push that operand (integer) into the stack. Else if we encounter an operator, then we shall pop two operands and save the first in op1 and next in op2 respectively. Further we call the function calculate.

The calculate function takes three inputs operand first, operator and operand second and then returns the final calculated value to its calling function. The value is then pushed into the stack.
We print the final remaining value at the top of the stack.

Below is the given C++ code for prefix expression evaluation:

#include <bits/stdc++.h>
typedef long long ll; // macro for long long
using namespace std;
ll calculate(ll op1, char op, ll op2); // Function to calculate the value of part of expression
int main()
{
  ll n; // User inputs n no of prefix expressions
  cin >> n;
  for (ll t = 0; t < n; t++)
  {
    string s;
    cin >> s;
    stack<ll> ch;
    for (ll i = s.length() - 1; i >= 0; i--)
    {
      if (s[i] == ',' && s[i - 3] == ',') // Condition to accept two digit no else ignore comma for single digit operand
      {
        ll temp;
        temp = 10 * s[i - 2] + s[i - 1];
        ch.push(temp);
        i = i - 2;
      }
      else if (isdigit(s[i])) // checks if character is digit or operator
      {
        ll temp = (ll)s[i];
        ch.push(temp);
      }
      else if (s[i] == '+' || (s[i] == '-' || (s[i] == '*' || (s[i] == '/'))))
      {
        ll op1, op2, res;
        op1 = ch.top() % 48;
        ch.pop(); // % 48 for conversion of character 'n' to integer n
        op2 = ch.top() % 48;
        ch.pop(); // 48 is ASCII code for character '0'
        res = calculate(op1, s[i], op2);
        ch.push(res);
      }
    }
    cout << ch.top() << endl; // The top of stack holds the result
  }
  return 0;
}
ll calculate(ll op1, char op, ll op2)
{
  if (op == '+')
    return op1 + op2;
  else if (op == '-')
    return op1 - op2;
  else if (op == '*')
    return op1 * op2;
  else if (op == '/')
    return op1 / op2;
}

For the input:

5
*,2,3
*23
+,*,2,+,/,14,2,5,1
-,*,6,3,-,4,1
+,+,2,6,+,-,13,2,4

The output becomes:

6
6
25
15
23

If you look at the for loop carefully, we have done %48 (modulus). The reason is that the ASCII code for character ‘0’ is 48, so for converting character to integer we have to either subtract 48 from ASCII code of scanned character or take modulus 48 to get the desired integer.

You may also like to learn:

Leave a Reply

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