The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

Stacks & Queues

Problem :-
Implement an algorithm to evaluate a postfix expression.

Solution :-
We will use a stack to implement a very basic solution which works only for single digit integers. There is no error handling as well.
1) Scan the expression from left to right.
2) If an operand is seen, push it onto stack.
3) If an operator is seen, pop of top two elements (operands) [ x & y ] from stack and perform z = x operand y . Push z onto stack.
4) Repeat steps (2) & (3) till scanning is over.

#include<iostream>
#include<cctype>
#include<stack>
using namespace std;

// returns the value when a specific operator
// operates on two operands
int eval(int op1, int op2, char operate) {
   switch (operate) {
      case '*': return op2 * op1;
      case '/': return op2 / op1;
      case '+': return op2 + op1;
      case '-': return op2 - op1;
      default : return 0;
   }
}

// evaluates the postfix operation
// this module neither supports multiple digit integers
// nor looks for valid expression
// However it can be easily modified and some additional
// code can be added to overcome the above mentioned limitations
// it's a simple function which implements the basic logic to
// evaluate postfix operations using stack
int evalPostfix(char postfix[], int size) {
   stack<int> s;
   int i = 0;
   char ch;
   int val;
   while (i < size) {
      ch = postfix[i];
      if (isdigit(ch)) {
         // we saw an operand
         // push the digit onto stack
         s.push(ch-'0');
      }
      else {
         // we saw an operator
         // pop off the top two operands from the
         // stack and evalute them using the current
         // operator
         int op1 = s.top();
         s.pop();
         int op2 = s.top();
         s.pop();
         val = eval(op1, op2, ch);
         // push the value obtained after evaluating
         // onto the stack
         s.push(val);
      }
      i++;
   }
   return val;
}

// main
int main() {
   char postfix[] = {'5','6','8','+','*','2','/'};
   int size = sizeof(postfix);
   int val = evalPostfix(postfix, size);
   cout<<"\nExpression evaluates to "<<val;
   cout<<endl;
   return 0;
}

Back | Next

All problems on Stacks and Queues
* Implement a stack using an array
* Implement a queue using an array
* Implement a circular queue using an array
* Design and implement an extended stack using linked list which permits push, pop & maxElement (gets maximum element in the stack) in O(1) time complexity
* Implement a circular queue using linked list
* Implement a Queue data structure using two stacks
* Sort a Queue using two stacks
* Convert infix expression to the postfix notation
* Implement an algorithm to evaluate a postfix expression
* Given a stack with only 0s & 1s, find the majority element in the stack
* Implement an inplace algorithm to sort a stack