C++ Progam to Evaluate a Prefix Expression














































C++ Progam to Evaluate a Prefix Expression



Algorithm to evaluate Prefix Expression:

The evaluation of prefix expression requires a stack data structure. We will push the operators in the stack and then solve the expression.

We will visit each element of the expression one by one. If the current element is an operand, we will push it to the stack. And if it is an operator, we will pop two operands, perform the operation, operand operator operand and then push the result back to the stack.

Program:

#include <bits/stdc++.h>

using namespace std;

double evaluatePrefix(string prefixExp) {

    stack<double> operendStack;

    int size = prefixExp.size() - 1;

    for (int i = size; i >= 0; i--) {

    if (isdigit(prefixExp[i]))

         operendStack.push(prefixExp[i] - '0');

      else {

         double o1 = operendStack.top();

         operendStack.pop();

         double o2 = operendStack.top();

         operendStack.pop();

         if( prefixExp[i] == '+')

            operendStack.push(o1 + o2);

         else if( prefixExp[i] == '-')

            operendStack.push(o1 - o2);

         else if( prefixExp[i] == '*')

            operendStack.push(o1 * o2);

         else if( prefixExp[i] == '/')

            operendStack.push(o1 / o2);

         else{

            cout<<"Invalid Expression";

            return -1;

         }

      }

   }

   return operendStack.top();

}


int main()

{

   string prefixExp = "*+69-31";

   cout<<"The result of evaluation of expression "<<prefixExp<<" is "<<evaluatePrefix(prefixExp);

   return 0;

}

Output:

The result of evaluation of expression *+69-31 is 30


More Articles of Shaik Aftab Ahmed:

Name Views Likes
C++ Program to Find the Frequency of Odd & Even Numbers in the given Matrix 238 1
C++ program to Sort a Linked List Using Merge Sort 225 1
C++ Program to Implement a Linked List representation of a Binary tree 221 1
C++ Program to Check for balanced parentheses in an expression 146 1
C++ Program to Perform Inorder, Preorder, Postorder traversals in a binary tree. 181 1
C++ program to print Indian flag 200 1
C++ program to Convert a multi level linked list to a singly linked list 151 1
C++ program to print right view of a Binary tree using queue 162 1
C++ Program to implement Huffman Coding Compression Algorithm 225 1
C++ Program to Create a Height Balanced Binary Tree 160 1
C++ program to implement Prims algorithm 234 1
C++ Program for BFS Traversal 173 1
C++ Progam to Evaluate a Prefix Expression 167 1
C++ Program to Implement Queue using Linked List 174 1
C++ implementation of Stack using Linked list 173 1
C++ program to find the intersection point of two linked lists 227 1
C++ program to count the inversions in the given array 214 1
C++ program to perform D.N.F sort 227 1
C++ program to print all possible subsets of a String 214 1
C++ program to count the number of ones in a binary representation of a number 229 1
C++ program to print all possible subsets of a set 246 1
C++ program to find the largest word in a String 220 1
C++ Program to print a matrix in Spiral order 228 1
C++ program to convert from Binary to Decimal, Octal to Decimal, Hexadecimal to Decimal 227 1
C limits library 254 1
Program to add two Binary numbers 231 1

Comments