# Evaluation of Postfix Expression

Difficulty Level Medium
StackViews 366

In the Evaluation of the postfix expression problem, we have given a string s containing a postfix expression. Evaluate the given expression.

## Example

Input : s = “231*+9-”

Output : -4

Input : s = “100 200 + 2 / 5 * 7 +”

Output : 757

## For Operands Having Single Digits

### Algorithm

1. Initialize a string s containing postfix expression.
2. Create a stack of the same size as that of the string.
3. 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.
4. Else pop the top two elements in the stack. Apply the current character/operator on them and push their result in the stack.
5. 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

1. Initialize a string s containing postfix expression.
2. Create a stack of the same size as that of the string.
3. If there is no stack return -1. Else traverse through the string and check if the current character is white space continues the loop.
4. 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.
5. Else pop the top two elements in the stack. Apply the current character/operator on them and push their result in the stack.
6. 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.

Translate »