In the Evaluation of the postfix expression problem, we have given a string s containing a postfix expression. Evaluate the given expression.
Table of Contents
Example
Input : s = “231*+9-”
Output : -4
Input : s = “100 200 + 2 / 5 * 7 +”
Output : 757
For Operands Having Single Digits
Algorithm
- Initialize a string s containing postfix expression.
- Create a stack of the same size as that of the string.
- If there is no stack return -1. Else traverse through the string and check if the current character is a digit, push the digit in the stack.
- Else pop the top two elements in the stack. Apply the current character/operator on them and push their result in the stack.
- Return the top of the stack.
C++ Program for Evaluation of Postfix Expression
#include <iostream>
#include <string.h>
using namespace std;
struct Stack{
int top;
unsigned capacity;
int* array;
};
struct Stack* createStack( unsigned capacity ){
struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));
if(!stack){
return NULL;
}
stack->top = -1;
stack->capacity = capacity;
stack->array = (int*) malloc(stack->capacity * sizeof(int));
if(!stack->array){
return NULL;
}
return stack;
}
int isEmpty(struct Stack* stack){
return stack->top == -1 ;
}
char peek(struct Stack* stack){
return stack->array[stack->top];
}
char pop(struct Stack* stack){
if(!isEmpty(stack)){
return stack->array[stack->top--];
}
return '$';
}
void push(struct Stack* stack, char op){
stack->array[++stack->top] = op;
}
int evaluatePostfix(char* exp){
struct Stack* stack = createStack(strlen(exp));
int i;
if(!stack){
return -1;
}
for(i = 0; exp[i]; ++i){
if(isdigit(exp[i])){
push(stack, exp[i] - '0');
}
else{
int val1 = pop(stack);
int val2 = pop(stack);
switch (exp[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 s[] = "231*+9-";
cout<<evaluatePostfix(s);
return 0;
}-4
Java Program for Evaluation of Postfix Expression
import java.util.Stack;
class Postfix{
static int evaluatePostfix(String exp){
Stack<Integer> stack=new Stack<>();
for(int i=0;i<exp.length();i++){
char c=exp.charAt(i);
if(Character.isDigit(c)){
stack.push(c - '0');
}
else{
int val1 = stack.pop();
int val2 = stack.pop();
switch(c){
case '+':
stack.push(val2+val1);
break;
case '-':
stack.push(val2- val1);
break;
case '/':
stack.push(val2/val1);
break;
case '*':
stack.push(val2*val1);
break;
}
}
}
return stack.pop();
}
public static void main(String[] args){
String s = "231*+9-";
System.out.println(evaluatePostfix(s));
}
}-4
Complexity Analysis
Time Complexity: O(n) where n is the size of the given string/expression.
Auxiliary Space: O(n) because we used the stack space for n characters.
For Operands Having Multiple Digits
Algorithm
- Initialize a string s containing postfix expression.
- Create a stack of the same size as that of the string.
- If there is no stack return -1. Else traverse through the string and check if the current character is white space continues the loop.
- If the current character is a digit, check if it’s a number read the full number else read the digit and push the digit in the stack.
- Else pop the top two elements in the stack. Apply the current character/operator on them and push their result in the stack.
- Return the top of the stack.
C++ Program for Evaluation of Postfix Expression
#include <iostream>
#include <string.h>
using namespace std;
class Stack{
public:
int top;
unsigned capacity;
int* array;
};
Stack* createStack( unsigned capacity ){
Stack* stack = new Stack();
if(!stack){
return NULL;
}
stack->top = -1;
stack->capacity = capacity;
stack->array = new int[(stack->capacity * sizeof(int))];
if(!stack->array){
return NULL;
}
return stack;
}
int isEmpty(Stack* stack){
return stack->top == -1 ;
}
int peek(Stack* stack){
return stack->array[stack->top];
}
int pop(Stack* stack){
if(!isEmpty(stack)){
return stack->array[stack->top--];
}
return '$';
}
void push(Stack* stack,int op){
stack->array[++stack->top] = op;
}
int evaluatePostfix(char* exp){
Stack* stack = createStack(strlen(exp));
int i;
if(!stack){
return -1;
}
for(i = 0; exp[i]; ++i){
if(exp[i] == ' '){
continue;
}
else if(isdigit(exp[i])){
int num=0;
while(isdigit(exp[i])){
num = num * 10 + (int)(exp[i] - '0');
i++;
}
i--;
push(stack,num);
}
else{
int val1 = pop(stack);
int val2 = pop(stack);
switch (exp[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 s[] = "100 200 + 2 / 5 * 7 +";
cout<<evaluatePostfix(s);
return 0;
}757
Java Program for Evaluation of Postfix Expression
import java.util.Stack;
class Postfix{
static int evaluatePostfix(String exp){
Stack<Integer> stack = new Stack<>();
for(int i = 0; i < exp.length(); i++){
char c = exp.charAt(i);
if(c == ' '){
continue;
}
else if(Character.isDigit(c)){
int n = 0;
while(Character.isDigit(c)){
n = n*10 + (int)(c-'0');
i++;
c = exp.charAt(i);
}
i--;
stack.push(n);
}
else{
int val1 = stack.pop();
int val2 = stack.pop();
switch(c){
case '+':
stack.push(val2+val1);
break;
case '-':
stack.push(val2- val1);
break;
case '/':
stack.push(val2/val1);
break;
case '*':
stack.push(val2*val1);
break;
}
}
}
return stack.pop();
}
public static void main(String[] args){
String s = "100 200 + 2 / 5 * 7 +";
System.out.println(evaluatePostfix(s));
}
}757
Complexity Analysis
Time Complexity: O(n) where n is the size of the given string/expression.
Auxiliary Space: O(n) because we used the stack space for n characters.