APPLICATIONS OF STACK:
The following are some of the applications of stack. They
are:
1. Paranthesis matching
2. Evaluation of postfix expression
3. Infix to prefix
4. Infix to postfix
5. Recursion
The objective of this function is to
check the matching of paranthesis in an expression i.e., in an
expression the number of left paranthesis must be equal to number of left paranthesis
must be equal to number of right paranthesis.
1 2 2 1
This is valid expression because in
this the number of left paranthesis (1,2) is equal to the number of right
paranthesis(2,1).
Eg:
((A+B)*C
1 2 2 This is not a valid expression because in this the number of left paranthesis (1, 2) is not equal to the number of right paranthesis (2).
CONVERSIONS
OF EXPRESSIONS:
Arithmetic
expressions can be represented in 3 ways.
INFIX expression or notations A+B
PREFIX expression or notations +AB
POSTFIX expression or notations AB+
1. ()
2. ^ 0r $
3 * / Left to right
4 + - Left to right
1.INFIX EXPRESSION
OR NOTATION : If the operator is placed between the operand then it is called Infix
expression or notation. They can be converted into postfix and prefix
Eg: A + B
A,B are Operands
+ operator
2.PREFIX NOTATION: If the operator is placed before the operands then it is called prefix expression. This is also called as polish expression.
Eg: +A B
A,B are Operand
+ operator
3.POSTFIX NOTATION: If the operator is
placed after the operands then it is called postfix expression. This is also
called REVERSE POLISH notation.
Eg: AB +
A,B are Operands
+ operator
PRECEDENCE OF OPERATORS for INFIX to POSTFIX
PRECEDENCE OPERATORS
1. ()
2. ^ 0r $
3 * / Left to right
4 + - Left to right
Example:
Convert A * B +C / D into Postfix
without using stack :
Step 1: Assign precedence priority first to the given expression
1 3 2
Step 2: Perform Postfix to the above expression as per precedence priority
AB* + CD/
AB*CD/+ POSTFIX
with using stack :
Symbols Stack Symbols Expression
A # A
* # * A
B # * * > + AB
+ # + AB*
C # + +</ AB*C
/ # + / AB*C
D # + / AB*CD
# AB*CD/+
PRECEDENCE OF OPERATORS for INFIX to PREFIX
PRECEDENCE OPERATORS
1. ()
2. ^ 0r $
3 * / RIGHT TO LEFT
4 + - RIGHT TO LEFT
Example:
Convert A * B +C / D into PREFIX
without using stack :
Step 1: Assign precedence priority first to the given expression
2 3 1
Step 2: Perform PREFIX to the above expression as per precedence priority
*AB + /CD
+*AB/CD PREFIX
with using stack :
IN ORDER TO CONVERT THE GIVEN INFIX EXPRESSION IS A * B + C / D INTO PREFIX
STEP1:
REVERSE THE GIVEN EXPRESSION D / C + B * A
STEP 2:
Symbols Stack Symbols Expression
D # D
/ # / D
C # / />+ DC/
+ # + DC/
B # + +<* DC/B
* # + * DC/B
A # + * DC/BA
# DC/BA*+
STEP3:
REVERSE THE POSTFIX EXPRESSION: +*AB/CD
NOTE: When converting from one notation to other notation
operators which have highest precedence are converted first and once it is
converted the remaining portion of the expression is considered as operands for
next process.
CONVERTING INFIX EXPRESSION TO POSTFIX EXPRESSION
The rules to be remembered to be infix to postfix are:
1) Paranthesize the expression starting from left to
right.
2) During paranthesize the expression the operands
associated with operator having higher precedence are first paranthesized.
For eg: A+(B*C)
3) Sub expressions (remaining part ) which has been
converted into postfix is to be treated as single operand.
4) once expression is converted to postfix form remove the
paranthesis.
import java.util.*;
public class Toh
{
public static void main(String args[])
{
int n;
Scanner toh = new Scanner(System.in);
System.out.printf("\n Enter no. of disks to be moved:\n");
n=toh.nextInt();
hanoi(n,'X','Z','Y');
}
static void hanoi(int n,char initial,char last,char temp)
{
if(n==1)
{
System.out.printf("move disk 1 from needle %c to %c\n",initial,last);
return;
}
hanoi(n-1,initial,temp,last);
System.out.printf("move disk %d from needle %c to %c\n",n,initial,last);
hanoi(n-1,temp,last,initial);
}
}
output:
No comments:
Post a Comment