stack datastructure
01.Evolution of postfix expression:
import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.Stack;
class Test1
{
// Method to evaluate value of a postfix expression
static int evaluatePostfix(String exp)
{
Stack<Integer> stack = new Stack<>();
for(int i = 0; i < exp.length(); i++)
{
int te= exp.charAt(i) - '0';
if(te>=0 && te<=9) stack.push(te);
else
{
int a = stack.pop();
int b = stack.pop();
if(exp.charAt(i)=='+') stack.push(b+a);
if(exp.charAt(i)=='-') stack.push(b-a);
if(exp.charAt(i)=='*') stack.push(b*a);
if(exp.charAt(i)=='/') stack.push(b/a);
}
}
return stack.pop();
}
// Driver program to test above functions
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
for(int i=0;i<n;i++)
{
String exp=sc.next();
System.out.println(evaluatePostfix(exp));
}
}
}
2:Infix to postfix using stack
import java.util.*;
import java.lang.*;
import java.io.*;
class infixtopost
{
public static int prec(char ch)
{
switch(ch)
{
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
}
return -1;
}
public static void infixToPostFix (char a[])
{
Stack<Character> s1=new Stack<Character>();
for(int i=0;i<a.length;i++)
{
if(prec(a[i])==-1 && a[i]!='(' && a[i]!=')')
{
System.out.print(a[i]);
}
else
{
if(a[i]=='(')
{
s1.push(a[i]);
}
else if(a[i]==')')
{
while(!s1.isEmpty() && s1.peek()!='(')
{
System.out.print(s1.pop());
}
s1.pop();
}
else
{
while(!s1.isEmpty() && prec(s1.peek()) >=prec(a[i]))
{
System.out.print(s1.pop());
}
s1.push(a[i]);
}
}
}
while(!s1.isEmpty())
{
System.out.print(s1.pop());
}
}
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
infixToPostFix(ab.next().toCharArray());
System.out.println();
}
}
}
Sort a stack
class SortStack
{
// This function return the sorted stack
public static Stack<Integer> sortstack(Stack<Integer>input)
{
Stack<Integer> tmpStack = new Stack<Integer>();
while(!input.isEmpty())
{
// pop out the first element
int tmp = input.pop();
// while temporary stack is not empty and
// top of stack is greater than temp
while(!tmpStack.isEmpty() && tmpStack.peek()
> tmp)
{
// pop from temporary stack and
// push it to the input stack
input.push(tmpStack.pop());
}
// push temp in tempory of stack
tmpStack.push(tmp);
}
return tmpStack;
}
Using recursion:
class GfG
{
public static void sortStack(Stack<Integer> s,int a)
{
if(s.isEmpty() || a>s.peek())
{
s.push(a);
return;
}
int temp=s.pop();
sortStack(s,a);
s.push(temp);
}
public Stack<Integer> sort(Stack<Integer> s)
{
if(!s.isEmpty())
{
int a=s.pop();
sort(s);
sortStack(s,a);
}
return s;
}
}
Area of histogram
class Solution {
public int largestRectangleArea(int[] h) {
int n=h.length,i=0,maxarea=0;
Stack<Integer> s=new Stack<Integer>();
while(i<n)
{
while(!s.isEmpty() && h[i]<h[s.peek()])
{
maxarea=Math.max(maxarea,h[s.pop()]* (i-(s.isEmpty()?0:s.peek() + 1)));
}
s.push(i++);
}
while(!s.isEmpty())
{
maxarea=Math.max(maxarea,h[s.pop()]*(n-(s.isEmpty()?0:s.peek()+1)));
}
return maxarea;
}
}
Comments
Post a Comment