Infix notation : we write expression in infix notation, for example: a-b+c , where
operators are used in between operands . It is easy for us humans to read,
write, and speak in infix notation but the same does not do well with computing
devices. An algorithm to process infix notation could be difficult and costly
in items of time and space consumption.
Prefix notation : In this notation ,the operator is
prefixed to operands i.e. operator is written ahead of operands . for example
+ab. This is equivalent to its infix notation a+b. Prefix notation is also known as POLISH NOTATION.
Postfix notation : In this notation ,the operator is postfixed to the
operands i.e., the operator is written after the operands . for example ab+. This
is equivalent to its infix notation a+b .
Postfix notation is also known as REVERSE POLISH NOTATION.
Conversion of an infix expression to its prefix form.
step 1: Consider the given INfix expression
A^B*C-D+E/F(G+H)
step 2: Reverse the given INfix expression
(H+G)F/E+D-C*B^A
|
Symbol Scanned |
Stack |
POSTfix expression |
|
( |
#( |
|
|
H |
#( |
H |
|
+ |
#(+ |
H |
|
G |
#(+ |
HG |
|
) |
# |
HG+ |
|
F |
# |
HG+F |
|
/ |
#/ |
HG+F |
|
E |
#/ |
HG+FE |
|
+ |
#+ |
HG+FE/ |
|
D |
#+ |
HG+FE/D |
|
- |
#+- |
HG+FE/D |
|
C |
#+- |
HG+FE/DC |
|
* |
#+-* |
HG+FE/DC |
|
B |
#+-* |
HG+FE/DCB |
|
^ |
#+-*^ |
HG+FE/DCB |
|
A |
#+-*^ |
HG+FE/DCBA |
|
# |
|
HG+FE/DCBA^*-+ |
Reverse the obtained POSTfix expression and that expression is the PREfix expression +-*^ABCD/EF+GH
class intopre
{
//Driver code
public static void main(String args[])
{
String s = "((a+b)^c-(d*e)/f)";
System.out.println( infixToPrefix(s));
}
// Function to check if given character is an operator or not.
static boolean isOperator(char c)
{
return (!(c >= 'a' && c <= 'z') && !(c >= '0' && c <= '9') && !(c >= 'A' && c <= 'Z'));
}
// Function to find priority of given operator.
static int getPriority(char C)
{
if (C == '-' || C == '+')
return 1;
else if (C == '*' || C == '/')
return 2;
else if (C == '^')
return 3;
return 0;
}
// Function that converts infix expression to prefix expression.
static String infixToPrefix(String infix)
{
// stack for operators.
Stack<Character> operators = new Stack<Character>();
// stack for operands.
Stack<String> operands = new Stack<String>();
for (int i = 0; i < infix.length(); i++)
{
// If current character is an
// opening bracket, then
// push into the operators stack.
if (infix.charAt(i) == '(')
{
operators.push(infix.charAt(i));
}
// If current character is a
// closing bracket, then pop from
// both stacks and push result
// in operands stack until
// matching opening bracket is
// not found.
else if (infix.charAt(i) == ')')
{
while (!operators.empty() &&
operators.peek() != '(')
{
// operand 1
String op1 = operands.peek();
operands.pop();
// operand 2
String op2 = operands.peek();
operands.pop();
// operator
char op = operators.peek();
operators.pop();
// Add operands and operator
// in form operator +
// operand1 + operand2.
String tmp = op + op2 + op1;
operands.push(tmp);
}
// Pop opening bracket
// from stack.
operators.pop();
}
// If current character is an
// operand then push it into
// operands stack.
else if (!isOperator(infix.charAt(i)))
{
operands.push(infix.charAt(i) + "");
}
// If current character is an
// operator, then push it into
// operators stack after popping
// high priority operators from
// operators stack and pushing
// result in operands stack.
else
{
while (!operators.empty() &&
getPriority(infix.charAt(i)) <=
getPriority(operators.peek()))
{
String op1 = operands.peek();
operands.pop();
String op2 = operands.peek();
operands.pop();
char op = operators.peek();
operators.pop();
String tmp = op + op2 + op1;
operands.push(tmp);
}
operators.push(infix.charAt(i));
}
}
// Pop operators from operators
// stack until it is empty and
// operation in add result of
// each pop operands stack.
while (!operators.empty())
{
String op1 = operands.peek();
operands.pop();
String op2 = operands.peek();
operands.pop();
char op = operators.peek();
operators.pop();
String tmp = op + op2 + op1;
operands.push(tmp);
}
// Final prefix expression is
// present in operands stack.
return operands.peek();
}
}
output:
a) +
b) $
c) ^
d) &
a) +
b) $
c) |
d) &
What would be the solution to the given prefix notation?
- + 5 / 10 5 5
a) 2
b) 5
c) 10
d) 7
Answer: a
Explanation: Reverse the given prefix expression 5 5 10 / 5 + -
Symbol Stack
5 5
5 5 5
10 5 5 10
/ 5 10/5
5 5 2 5
+ 5 5+2
- 5 7
7-5
2
Note: top of stack operand operator bottom of stack
What would be the solution to the given prefix notation?
- * 1 5 / * / 6 3 6 2
a) 1
b) 0
c) -1
d) -2
Answer:c
Explanation: Reverse the given prefix expression 2 6 3 6 / * / 5 1 * -
Symbol Stack
2 2
6 2 6
3 2 6 3
6 2 6 3 6
/ 2 6 6/3
2 6 2
* 2 2*6
2 12
/ 12/2
6
5 6 5
1 6 5 1
* 6 1*5
6 5
- 5-6
-1
Note: top of stack operand operator bottom of stack
No comments:
Post a Comment