Infix to Postfix and Prefix Conversions
The following ApplicationOfStack class consists the following methods:
- boolean isOperator(char op): To check whether the character is an operator or not.
- int precedence(char ch): Returns the precedence of operators.
- boolean isOpeningBracket(char ch): To check whether the character is an opening bracket or not.
- boolean isClosingBracket(char ch): To check whether the character is an closing bracket or not.
- String infixToPostfix(String str): Returns the postfix expression of a infix expression.
- String replaceBrackets(String str): Replaces an opening bracket with a closing bracket and vice-versa.
- String infixToPrefix(String str): Returns the prefix expression of a infix expression.
import java.util.Stack;
class ApplicationOfStack {
boolean isOperator(char op) {
switch (op) {
case '+':
case '-':
case '*':
case '/':
case '%':
return true;
default:
return false;
}
}
int precedence(char ch) {
switch (ch) {
case '+':
case '-':
return 0;
case '*':
case '/':
case '%':
return 1;
default:
return -1;
}
}
boolean isOpeningBracket(char ch) {
switch (ch) {
case '(':
case '[':
case '{':
return true;
default:
return false;
}
}
boolean isClosingBracket(char ch) {
switch (ch) {
case ')':
case ']':
case '}':
return true;
default:
return false;
}
}
String infixToPostfix(String str) {
Stack<String> stack = new Stack<String>();
String word = "";
String postfix = "";
for (int i = 0; i < str.length(); i++) {
word += str.charAt(i);
if (str.charAt(i) == ' ' || i == str.length() - 1) {
if (isOpeningBracket(word.charAt(0)))
stack.push(word.substring(0, 1));
else if (isClosingBracket(word.charAt(0))) {
if (word.charAt(0) == ')') {
while (stack.peek().charAt(0) != '(')
postfix += stack.pop() + " ";
stack.pop();
} else if (word.charAt(0) == ']') {
while (stack.peek().charAt(0) != '[')
postfix += stack.pop() + " ";
stack.pop();
} else {
while (stack.peek().charAt(0) != '{')
postfix += stack.pop() + " ";
stack.pop();
}
} else if (isOperator(word.charAt(0))) {
if (stack.isEmpty())
stack.push(word.substring(0, 1));
else if (precedence(word.charAt(0)) > precedence(stack.peek().charAt(0)))
stack.push(word.substring(0, 1));
else {
while (precedence(word.charAt(0)) < precedence(stack.peek().charAt(0)))
postfix += stack.pop() + " ";
stack.push(word.substring(0, 1));
}
} else
postfix += word.substring(0, word.length() - 1) + " ";
word = "";
}
}
while (!stack.isEmpty())
postfix += stack.pop() + " ";
return postfix;
}
String replaceBrackets(String str) {
String newStr = "";
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == '(')
newStr += ')';
else if (str.charAt(i) == ')')
newStr += '(';
else
newStr += str.charAt(i);
}
return newStr;
}
String infixToPrefix(String str) {
str = new StringBuffer(str).reverse().toString();
str = replaceBrackets(str);
str = infixToPostfix(str);
str = new StringBuffer(str).reverse().toString();
return str;
}
}
Evaluation of Postfix and Prefix expressions
The following ApplicationOfStack class consists the following methods:
- boolean isOperator(char op): To check whether the character is an operator or not.
- int solve(int op1, int op2, char op): Returns the result of the operation between two operands.
- void prefixEvaluation(String str): Returns the value of prefix expression.
- void postfixEvaluation(String str): Returns the value of postfix expression.
import java.util.Stack;
class ApplicationOfStack {
boolean isOperator(char op) {
switch (op) {
case '+':
case '-':
case '*':
case '/':
case '%':
return true;
default:
return false;
}
}
int solve(int op1, int op2, char op) {
switch (op) {
case '+':
return op1 + op2;
case '-':
return op1 - op2;
case '*':
return op1 * op2;
case '/':
return op1 / op2;
case '%':
return op1 % op2;
default:
return -1;
}
}
void prefixEvaluation(String str) {
Stack<Integer> stack = new Stack<Integer>();
int op1, op2;
String word = "";
try {
for (int i = str.length() - 1; i > -1; i--) {
word += str.charAt(i);
if (str.charAt(i) == ' ' || i == 0) {
if (isOperator(word.charAt(0))) {
op1 = stack.pop();
op2 = stack.pop();
stack.push(solve(op1, op2, word.charAt(0)));
} else {
word = new StringBuffer(word).reverse().toString();
stack.push(Integer.parseInt(word.substring(1, word.length())));
}
word = "";
}
}
System.out.println(stack.peek());
} catch (Exception e) {
System.out.println("ERROR!!!");
}
}
void postfixEvaluation(String str) {
Stack<Integer> stack = new Stack<Integer>();
int op1, op2;
String word = "";
try {
for (int i = 0; i < str.length(); i++) {
word += str.charAt(i);
if (str.charAt(i) == ' ' || i == str.length() - 1) {
if (isOperator(word.charAt(0))) {
op1 = stack.pop();
op2 = stack.pop();
stack.push(solve(op2, op1, word.charAt(0)));
} else
stack.push(Integer.parseInt(word.substring(0, word.length() - 1)));
word = "";
}
}
System.out.println(stack.peek());
} catch (Exception e) {
System.out.println("ERROR!!!");
}
}
}
Parenthesis Matching
The following ApplicationOfStack class consists the following methods:
- boolean isOpeningBracket(char ch): To check whether the character is an opening bracket or not.
- boolean isClosingBracket(char ch): To check whether the character is an closing bracket or not.
- boolean isParenthesisMatching(String exp): Checks whether the parenthesis matches or not.
import java.util.Stack;
class ApplicationOfStack {
boolean isOpeningBracket(char ch) {
switch (ch) {
case '(':
case '[':
case '{':
return true;
default:
return false;
}
}
boolean isClosingBracket(char ch) {
switch (ch) {
case ')':
case ']':
case '}':
return true;
default:
return false;
}
}
boolean isParenthesisMatching(String exp) {
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < exp.length(); i++) {
if (isOpeningBracket(exp.charAt(i)))
stack.push(exp.charAt(i));
else if (isClosingBracket(exp.charAt(i))) {
if ((exp.charAt(i) == ')' && stack.pop() != '(') || (exp.charAt(i) == ']' && stack.pop() != '[')
|| (exp.charAt(i) == '}' && stack.pop() != '{'))
return false;
}
}
if (stack.isEmpty())
return true;
return false;
}
}
Tower of Hanoi
The fun puzzle game tower of Hanoi consists of three towers or rods and an N number of discs. The game aims to move all the discs from tower src to tower dest using tower helper following some rules.
The main three rules of the tower of Hanoi problem are as follows:
- We can move only one disc at a time.
- We can move only the uppermost disc of the stack.
- We can’t place a larger disc on top of a smaller disc.
void towerOfHanoi(int num, char src, char dest, char helper) {
if (num == 1) {
System.out.println("Moving from " + src + " to " + dest + ".");
return;
}
towerOfHanoi(num - 1, src, helper, dest);
System.out.println("Moving from " + src + " to " + dest + ".");
towerOfHanoi(num - 1, helper, dest, src);
}
Comments
Post a Comment