Hello! So I’m doing a 30 day coding challenge where I solve a few questions everyday and thought of posting them here on my blog so that you guys can join the challenge too!
Welcome to Coding challenge Day 1: Problem 2! Be sure to post your answers, queries etc in the comments!!
Problem: Evaluate a given posfix expression
Sample input: 214+*
Output: 10 ((1+4)*2)
Sample input: 82/
Output: 4 (8/2)
Sample Input: 264+*5/
Output: 4 ((2*(6+4))/5)
Solution:
- So here’s how the logic goes:
- I’ve made use of stack data structure
- Store your postfix expression in a character array
- Traverse the array and push all numeric data into stack
- As soon as you come across an arithmetic operator pop the top two elements and perform the operation
- push the result back into stack
Note: I’ve made use of JAVA in the following code
package stack;
public class Program005postfix {
static class Stack{
final int Max= 10;
int data[]= new int[Max];
int top=-1;
public void push (int element){
if(top<Max-1){
data[++top]= element;
}
else
System.out.println("Stack is full");
}
public Integer pop(){
if(top ==-1){
System.out.println("Stack is empty");
return null;
}
return data[top--];
}
}
public static int getvalue (char a){
int value= a -'0';
return value;
}
public static void postfix (char exp[]){
Stack S= new Stack();
int length = exp.length;
for(int i=0; i<length; i++){
char a= exp[i];
if(a>='0' && a<='9'){
int v = getvalue(a);
S.push(v);
}
else {
int t1= S.pop();
int t2= S.pop();
int value=0;
if(a=='+'){
value=t2+t1;
S.push(value);
}
else if(a=='-'){
value=t2-t1;
S.push(value);
}
else if(a=='*'){
value=t2*t1;
S.push(value);
}
else if(a=='/'){
value=t2/t1;
S.push(value);
}
else if(a=='%'){
value=t2%t1;
S.push(value);
}
}
}
Integer final_result = S.pop();
System.out.println(final_result);
}
public static void main (String [] args){
char exp[]= {'2', '6', '4','+', '*', '5','/'};
postfix(exp);
}
}
HAPPY LEARNING!!