Postfix expression evaluation using stacks
Infix 5 + 3
Prefix + 5 3
Postfix 5 3 +
Postfix 5 6 – 4 5 + * infix: (5-6) * (4 +5)
= -9
Example:
Evaluate the given Postfix expression 5 6 + 2 - using stack
infix 5+6-2 =9
5 6 + 2 -
Push(5) push(6) pop() pop() pus(11) push(2) pop() pop() push(9)
6 2
5 5 5 11 11 11 9
Evaluate the given Postfix expression 5 6 + 2 - using stack
7 4 - 8 10 / +
Push(7) push(4) pop() pop() push(3) push(8) push(10) pop() pop() push(0.8)
10
4 8 8 8 0.8
7 7 7 3 3 3 3 3 3
Pop() pop() push(3.8)
3 3.8
Stack Examples
Write a method stackShuffle to be in a class called StackApp that
accepts two parameters s1 of type ArrayStack and value of type E. The
method is going to reshuffle s1 in a way that the shuffling will be in
according to the following criteria:
If the element in the stack is greater than the value, it will be in the first
half of the stack, otherwise, it will be in the second half of the stack
(direction is starting from the top and go down as shown in the example
after the method call).
The method returns false if stack is empty, otherwise, it returns true.
The method head is
public static<E> boolean stackShuffle(ArrayStack<E> s1,E value)
Ex:
Before method call
S1
top
23 45 13 67 22 5 14 77
value is 40
After method call
S1
top
45 67 77 23 13 22 5 14
Required
Before After
S1 S1
23 45
45 67
13 77
67 23
22 13
5 22
14 5
77 14
Procedure
Create two stacks st1 and st2, st1 will be for elements > value and st2 for
elements < value
Pop from s1, if element > value push it into st1, else push it into st2
14
5
77 22
67 13
45 23
St1 St2
Pop from st2 and push into s1
Pop from st1 and push into s1
S1
45
67
77
23
13
22
5
14
public static<E> boolean stackShuffle(ArrayStack<E> s1,E value)
{
if ([Link]()) return false;
ArrayStack<E> st1= new ArrayStack<E>();
ArrayStack<E> st2= new ArrayStack<E>();
while(![Link]())
{
if(((Comparable)[Link]()).compareTo((Comparable) value)> 0)
[Link]([Link]());
else
[Link]([Link]());
}
while (! [Link]())
[Link]([Link]());
while(! [Link]())
[Link]([Link]());
return true;
}
Write a method matchAndUpdate to be outside the ArrayStack class
that has two parameters St1 and St2 of type Arraystack with integer
data elements and a third parameter value of type int. The method is to
change the values of st1 if there is a full match between St1 and St2 (all
elements in St1 and St2 are the same and in the same order), St1 will
change in a way that value will be added to every element in St1. If no
full match, the method returns false, otherwise it returns true. Assume
St1 and St2 are of the same size. Assume further that you have
accessibility to ArrayStack class methods only and not allowed to use
arrays. The method head is
public boolean static matchAndUpdate(ArrayStack<Integer> St1,
ArrayStack<Integer> St2, int value);
Ex:
St1:
top
2 5 7 8 9
St2:
top
2 5 7 8 9
Value is 2
After method call
St1:
top
4 7 9 10 11
St2:
2 5 7 8 9
2 2
5 5
7 7
8 8
9 9
St1 st2
4 2
7 5
9 7
10 8
11 9
St1 st2
Procedure
2 2
5 5
7 7
8 8
9 9
st1 st2
create two stacks st11 as st1 and st22 as st2 using copy constructor
2 2
5 5
7 7
8 8
9 9
St11 st22
Keep poping from st11 and st22 and compare them if not in the same
order, return false. If all are equal st11 and st22 will be empty.
St11 st22
Pop from st1 (st1 becomes empty) and push in st11 after adding the
value
11
10
9
7
4
St1 st11
Pop from st11 (becomes empty) and push into st1
4
7
9
10
11
St1 st11
public static boolean matchAndUpdate(ArrayStack<Integer> St1,
ArrayStack <Integer> St2, int value)
{ ArrayStack<Integer> St11= new ArrayStack<Integer>(St1);
ArrayStack<Integer> St22= new ArrayStack<Integer>(St2);
if ([Link]()) return false;
while (! [Link]())
if (! [Link]().equals([Link]())) return false;
while (! [Link]())
[Link]([Link]()+value);
while( ![Link]())
[Link]( [Link]());
return true;
}
Write a method reverseEquality to be considered outside the arrayStack
class that accepts two parameters St1 and St2 of type ArrayStack, the
method returns true if both St1 and St2 are in the reverse order,
otherwise, it returns false. Assume St1 and St2 are of the same size.
The method head is
public static <E> boolean reverseEquality(ArrayStack<E> St1, ArrayStack <E> St2)
st1:
top
5 6 7 9
St2:
top
9 7 6 5
Solution:
St11: 5 6 7 9
St22 : 9 7 6 5 st22: (pop from st22 and push into St2reverse)
St2reverse: St2Reverse: 5 6 7 9
Then compare st11 with st2Reverse
public static <E> boolean reverseEquality(ArrayStack<E> St1, ArrayStack
<E> St2)
{
/* we need to make copies so that we do not change in the original
stacks */
ArrayStack<E> St11= new ArrayStack<E>(St1);
ArrayStack<E> St22= new ArrayStack<E>(St2);
ArrayStack<E> St2Reverse = new ArrayStack<E>();
if ([Link]()) return false;
/* we reverse first one of the stacks so later we can compare if the they
are in the reverse order */
while (![Link]())
{
[Link]([Link]());
}
/* comparison process */
while(![Link]())
{
if ( ! [Link]().equals([Link]())) return false;
}
return true;
}
Write a method reverseEqualityAndFillStack to be considered outside the
ArrayStack class that accepts three parameters St1 , St2 and St3 of type
ArrayStack, the method checks if both St1 and St2 are in the reverse order, fill
St3 with St1 and St2 in the same order. Assume St1 and St2 are of the same
size. If filling is done, the method returns true, otherwise, it returns false. The
method title is
public static <E> boolean reverseEqualityAndFillStack(ArrayStack<E> St1, ArrayStack <E> St2,
ArrayStack<E> St3)
public static <E> boolean reverseEqualityAndFillStack(ArrayStack<E> St1, ArrayStack <E> St2,
ArrayStack<E> St3)
{
/* instead of the part written in red we can call the method in the
previous question
if (reverseEquality(St1, St2)== false) return false;
*/
ArrayStack<E> St11= new ArrayStack<E>(St1);
ArrayStack<E> St22= new ArrayStack<E>(St2);
ArrayStack<E> St2Reverse = new ArrayStack<E>();
if ([Link]() || [Link]()) return false;
while (![Link]())
{
[Link]([Link]());
}
while(![Link]())
{
if ( ! [Link]().equals([Link]())) return false;
}
/* in this part we reverse each of st1 and st2 then push them into st3 so
they will be in the same original order */
ArrayStack<E> St1Reverse = new ArrayStack<E>();
ArrayStack<E> St111= new ArrayStack<E>(St1);
ArrayStack<E> St22Reverse = new ArrayStack<E>();
ArrayStack<E> St222= new ArrayStack<E>(St2);
while (! [Link]())
[Link]([Link]());
while(![Link]())
[Link]([Link]());
while (![Link]())
[Link]([Link]());
while(![Link]())
[Link]([Link]());
return true;
}
Write a method to be outside the ArrayStack class that accepts
one parameter value as integer, the method returns true if
value is palindrome, or otherwise it returns false. The method
head is
public static boolean Palindrom(int value)
121 palindrome
12321, 1331 palindrome
145 not palindrome
temp= 12321 temp1=temp temp%10 =1 temp =temp/10
= 1232
Stack: 1
temp%10= 2 temp= temp/10 = 123
stack: 2 1
temp%10 = 3 temp=temp/10 = 12
stack: 3 2 1
temp%10 = 2 temp=temp/10=1
stack: 2 3 2 1
temp%10 = 1 temp=temp/10 = 0
top
stack: 1 2 3 2 1
temp1=12321
temp1%10 = 1 temp1=temp1/10 = 12321
compare the pop from the stack with the reminder of temp1
and continue like this
public static boolean Palindrom(int value)
public static boolean Palindrom(int value)
{
int temp = value;
int rem;
ArrayStack<Integer> st = new ArrayStack<Integer>();
/* partition the number into digits and from left to right and push them
into the stack */
do
{
rem = temp %10;
[Link](rem);
temp=temp/10;
} while (temp>0);
/* Now take the number and partition it again, the digit which you get
should be equal to the value poped from the stack if palindom */
temp=value;
while (! [Link]())
{
rem = temp %10;
temp=temp/10;
if ([Link]() != rem) return false;
}
return true;
}
Another Solution
public static boolean Palindrom (int value)
{
int temp=value;
int rem;
ArrayStack<Integer> st = new ArrayStack<Integer>();
int count=0;
do
{
rem = temp %10;
[Link](rem);
temp=temp/10;
count++;
} while (temp>0);
ArrayStack<Integer> streverse1 = new ArrayStack<Integer>();
ArrayStack<Integer> st11= new ArrayStack<Integer>(st);
int i=0;
int size=count;
while (i < count/2)
{
[Link]([Link]());
i++;
}
if (size % 2!=0)
[Link]();
while(! [Link]())
{
if([Link]() != [Link]()) return false;
}
return true;
}
Write a method that is considered within the ArrayStack class.
The method finds the maximum element in the array and
makes it at the top of stack. The method head is
public void changeStack()
Example:
Befor method call
top
20 45 7 8 12 70 25
After method call
top
70 20 45 7 8 12 25
public void changeStack()
{
if (topOfStack == -1) return;
E[] temp= (E[]) new Object[topOfStack+1];
E max = theData[0];
int loc=0;
int i;
for( i=1; i < topOfStack+1; i++)
if (((Comparable) theData[i]).compareTo ((Comparable)
max)>0)
{ max=theData[i]; loc=i;}
for(i=0; i < loc; i++)
temp[i]=theData[i];
for(i=loc+1; i<topOfStack+1;i++)
temp[i-1] = theData[i];
temp[topOfStack]=max;
theData=temp;
}