//In the name of Allah
/*
Using the Stack and Recursive concept, develop a program to convert arithmetic expressions. The program should be able to:
- Convert from infix to postfix
- Convert infix to prefix
The program must prompt user input an arithmetic infix expression for conversion to either prefix or postfix. The conversion option is wholly dependent to the user; either to postfix or prefix.
---
Infix -> Postfix Rules:
R1: Object operatorStack is empty
R2: if operator, loop until the operator has been pushed onto the operatorStack
-if the operatorStack is empty, or operator have higher precedence than the operator on top of the operatorStack,
-push operator onto operatorStack
-else
-Pop the operatorStack and append that popped operator to the postfix string.
R3: Once reach the end of input string
-loop until operatorStack is empty
-pop the operatorStack object and append that popped operator to the postfix string
**Parentheses:
if leftParentheses "(",
pushed onto the operatorStack
but precedence is lower than any other binary operator
else if rightParenthese ")" is found
operator object is repeatedly popped
popped element appended to postfix string
until operator on top is leftParentheses "("
then that operator "(" is popped but not appended
continue scanning the infix string
Infix -> Prefix Rules:
iNew algorithm
1: Reverse the input string
2: Examine the next element in the input
3. If it is operand, add it into the output string
4. If it is closing parenthesis, push it on stack
5. If it is an operator, then
a. If stack.isEmpty, push operation on stack
b. if the top of the stack is ")", push operator on stack
c. if it has same or higher priority than the top of the stack, push it
d. else pop the operator & add it to output string, repeat 5
6. If it is "(" pop operator and add them to string s until a ")" is encountered . POP and discard ")"
7. If there is more input go to step 2
8. If there is no more input, unstack the remaining operators and add them
9. Reverse the output string
New algorithm
1. if operand push into operand stack
2. if operator
a. if stack is empty or ch="(", push into operator stack
b. if ")", CASE3 until reach "("
c. else, CASE3
3. if endofexpression, CASE3 until operator stack empty
4. return the only operand in operandStack
*Compile: javac 2009147897.java
*Run: java PostfixPrefixApp
Problems still arises1. Can't deal with expression with spaces in it E.g. [a + b]. Must use [a+b]
2. Program are too redundant at certain part: i++; and toPostfix(exp)
3. Thinking that this is more of the brute way rather than
the inteligent way. Maybe can be simplified
4. Operators limited to * / + - %
5. Looping of the program cause unexpected result
6. toPrefix() is not correct.
e.g: Didn't work for (a+b)+c+d, a+(c-h)/(b*d)
*/
import java.util.*;
class PostfixPrefixApp{
/**Global Variables**************************************/
private static Stack operatorStack= new Stack();
private static Stack operandStack= new Stack();
private static String postfix="";
private static String prefix="";
private static String temp="";
private static int i=0; //use i to iterate through infix string [exp.charAt(i)]
private static int menu=0;
public static void main (String [] args){
/**Local Variables***************************************/
Scanner scan = new Scanner(System.in);
String infix;
/**Menu**************************************************/
System.out.println ("\nChanging from infix to postfix or prefix notation.");
System.out.println ("----------");
System.out.println ("Menu");
System.out.println ("----------");
System.out.println ("1. Postfix");
System.out.println ("2. Prefix");
menu = scan.nextInt();
/**Postfix***********************************************/
if ( menu == 1){
System.out.println ("Infix to Postfix");
System.out.print ("Enter infix expression: ");
infix = scan.next();
postfix = toPostfix(infix);
System.out.println("Postfix: "+ postfix);
System.out.println ("----------");
}
/**Prefix************************************************/
else if ( menu == 2){
System.out.println ("Infix to Prefix");
System.out.print ("Enter infix expression: ");
infix = scan.next();// Storing the infix string
infix=reverse(toPrefix(reverse(infix)));
System.out.println("Prefix: "+infix);//display prefix string
}
/**Wrong input*******************************************/
else {
System.out.println ("Wrong input.");
System.out.println ("----------");
}
System.exit(0);
}
/**toPostfix*********************************************/
public static String toPostfix(String exp){
if (exp.length()==i){
/*
for when the infix has finished being processed
because iterate i for the usage of exp.charAt(i)
*/
while (! operatorStack.isEmpty()){
String temp = (String)operatorStack.peek();
if (temp.charAt(0)!='(')//if there is "(" in the operatorStack
postfix+=(String)operatorStack.pop();//pop all element into postfix string
else
operatorStack.pop();//removing "("
}
return postfix; //the last process of the recursion
}
else { //if the infix still being processed
String ch = exp.substring(i,i+1);
if (ch.charAt(0)==')'){//if opening parentheses "(", push it into stack
operatorStack.push(ch);
return redundantFunction(exp);// there are same processes that were simplified in this method instead. Refer "Problems arises"
// or refer the method redundantFunction() below
}
else if (ch.charAt(0)=='('){
/*
if found closing parentheses ')'
loop until reach '('
append poped element of operatorStack into postfix string
remove '(' from operatorStack
*/
String topOfoperatorStack = (String)operatorStack.peek();
while (! topOfoperatorStack.equals("(")){
//String a=(String)operatorStack.pop();
//System.out.println(a); //for testing process
postfix+=operatorStack.pop();
topOfoperatorStack = (String) operatorStack.peek();
}
operatorStack.pop();
//String c= (String) operatorStack.pop();
//System.out.println("c: "+c); //for testing if we correctly removing (
return redundantFunction(exp);
}
else if (isOperand(ch)){
/*
if an operand a-zA-Z atau digit \\d
directly appened to infix
*/
postfix+=ch;
return redundantFunction(exp);
}
else if (isOperator(ch)){
/*
if operators
if empty
directly push into operatorStack
else
see top of operatorStack
if higher precendence
directly push into operatorStack
else
pop topOfoperatorStack
append it to postfix string
push current operator into operatorStack
*/
if (operatorStack.isEmpty()){
operatorStack.push(ch);
return redundantFunction(exp);
}
else {
String topOfoperatorStack = (String)operatorStack.peek();
if (precendence(ch) > precendence(topOfoperatorStack)){
operatorStack.push(ch);
return redundantFunction(exp);
}
else {
postfix+=(String)operatorStack.pop();
operatorStack.push(ch);
return redundantFunction(exp);
}
}
}
else{
//catching all other possible situation supposedly
return redundantFunction(exp);
}
}
}
/**toPrefix**********************************************/
private static String toPrefix(String exp){
temp="";
if (iprecendence( (String) operatorStack.peek() )) ){
operatorStack.push(ch);
}
else{
temp=CASE3();
operandStack.push(temp);
}
}
//System.out.println(ch);//testing
return redundantFunction(exp);
}
else{
while(! operatorStack.isEmpty()){
temp=CASE3();
operandStack.push(temp);
}
//System.out.println("Who is it? : "+operandStack.peek());//testing
/*if (operandStack.isEmpty())//testing
return "operandStack.isEmpty()";
else*/
return (String) operandStack.pop();
}
}
/**isOperator********************************************/
private static boolean isOperator(String ch){//method to check operator
String operators = "*/%+-";
if (operators.indexOf(ch) != -1)
return true;
else
return false;
}
/**isOperand********************************************/
private static boolean isOperand(String ch){//check if it is alphanumeric - method taken from outside sources
if (ch.matches("[a-zA-Z]|\\d"))
return true;
else
return false;
}
/**precedence********************************************/
private static int precendence(String ch){//method that check the precendence of operator and return it
//value 1 or 2
String precendence2 = "*/%";
String precendence1 = "+-";
if (precendence2.indexOf(ch) != -1)
return 2;
else if (precendence1.indexOf(ch) != -1)
return 1;
else
return 0;
}
/**redundantFunction********************************************/
private static String redundantFunction(String exp){
/*redundant processes
need i to iterate through infix string while using recursion technique
*/
i++;
if (menu==1)
return toPostfix(exp); //the recursion part
else
return toPrefix(exp); //the recursion part
}
/**reverse********************************************/
private static String reverse(String exp){
Stack tempString = new Stack();
for (int index=0;index tempString.push( exp.charAt(index) );
}
exp="";
while (! tempString.isEmpty() ){
exp+= tempString.pop();
}
return exp;
}
private static String CASE3(){
String opt="",oprn1="",oprn2="";
opt += operatorStack.pop();
oprn1 += operandStack.pop();
if (operandStack.isEmpty())
oprn2+="";
else
oprn2 += operandStack.pop();
temp=opt+oprn2+oprn1;
//System.out.println("Temp:"+temp);
return temp;
}
}
/*
Using the Stack and Recursive concept, develop a program to convert arithmetic expressions. The program should be able to:
- Convert from infix to postfix
- Convert infix to prefix
The program must prompt user input an arithmetic infix expression for conversion to either prefix or postfix. The conversion option is wholly dependent to the user; either to postfix or prefix.
---
Infix -> Postfix Rules:
R1: Object operatorStack is empty
R2: if operator, loop until the operator has been pushed onto the operatorStack
-if the operatorStack is empty, or operator have higher precedence than the operator on top of the operatorStack,
-push operator onto operatorStack
-else
-Pop the operatorStack and append that popped operator to the postfix string.
R3: Once reach the end of input string
-loop until operatorStack is empty
-pop the operatorStack object and append that popped operator to the postfix string
**Parentheses:
if leftParentheses "(",
pushed onto the operatorStack
but precedence is lower than any other binary operator
else if rightParenthese ")" is found
operator object is repeatedly popped
popped element appended to postfix string
until operator on top is leftParentheses "("
then that operator "(" is popped but not appended
continue scanning the infix string
Infix -> Prefix Rules:
iNew algorithm
1: Reverse the input string
2: Examine the next element in the input
3. If it is operand, add it into the output string
4. If it is closing parenthesis, push it on stack
5. If it is an operator, then
a. If stack.isEmpty, push operation on stack
b. if the top of the stack is ")", push operator on stack
c. if it has same or higher priority than the top of the stack, push it
d. else pop the operator & add it to output string, repeat 5
6. If it is "(" pop operator and add them to string s until a ")" is encountered . POP and discard ")"
7. If there is more input go to step 2
8. If there is no more input, unstack the remaining operators and add them
9. Reverse the output string
New algorithm
1. if operand push into operand stack
2. if operator
a. if stack is empty or ch="(", push into operator stack
b. if ")", CASE3 until reach "("
c. else, CASE3
3. if endofexpression, CASE3 until operator stack empty
4. return the only operand in operandStack
*Compile: javac 2009147897.java
*Run: java PostfixPrefixApp
Problems still arises1. Can't deal with expression with spaces in it E.g. [a + b]. Must use [a+b]
2. Program are too redundant at certain part: i++; and toPostfix(exp)
3. Thinking that this is more of the brute way rather than
the inteligent way. Maybe can be simplified
4. Operators limited to * / + - %
5. Looping of the program cause unexpected result
6. toPrefix() is not correct.
e.g: Didn't work for (a+b)+c+d, a+(c-h)/(b*d)
*/
import java.util.*;
class PostfixPrefixApp{
/**Global Variables**************************************/
private static Stack operatorStack= new Stack();
private static Stack operandStack= new Stack();
private static String postfix="";
private static String prefix="";
private static String temp="";
private static int i=0; //use i to iterate through infix string [exp.charAt(i)]
private static int menu=0;
public static void main (String [] args){
/**Local Variables***************************************/
Scanner scan = new Scanner(System.in);
String infix;
/**Menu**************************************************/
System.out.println ("\nChanging from infix to postfix or prefix notation.");
System.out.println ("----------");
System.out.println ("Menu");
System.out.println ("----------");
System.out.println ("1. Postfix");
System.out.println ("2. Prefix");
menu = scan.nextInt();
/**Postfix***********************************************/
if ( menu == 1){
System.out.println ("Infix to Postfix");
System.out.print ("Enter infix expression: ");
infix = scan.next();
postfix = toPostfix(infix);
System.out.println("Postfix: "+ postfix);
System.out.println ("----------");
}
/**Prefix************************************************/
else if ( menu == 2){
System.out.println ("Infix to Prefix");
System.out.print ("Enter infix expression: ");
infix = scan.next();// Storing the infix string
infix=reverse(toPrefix(reverse(infix)));
System.out.println("Prefix: "+infix);//display prefix string
}
/**Wrong input*******************************************/
else {
System.out.println ("Wrong input.");
System.out.println ("----------");
}
System.exit(0);
}
/**toPostfix*********************************************/
public static String toPostfix(String exp){
if (exp.length()==i){
/*
for when the infix has finished being processed
because iterate i for the usage of exp.charAt(i)
*/
while (! operatorStack.isEmpty()){
String temp = (String)operatorStack.peek();
if (temp.charAt(0)!='(')//if there is "(" in the operatorStack
postfix+=(String)operatorStack.pop();//pop all element into postfix string
else
operatorStack.pop();//removing "("
}
return postfix; //the last process of the recursion
}
else { //if the infix still being processed
String ch = exp.substring(i,i+1);
if (ch.charAt(0)==')'){//if opening parentheses "(", push it into stack
operatorStack.push(ch);
return redundantFunction(exp);// there are same processes that were simplified in this method instead. Refer "Problems arises"
// or refer the method redundantFunction() below
}
else if (ch.charAt(0)=='('){
/*
if found closing parentheses ')'
loop until reach '('
append poped element of operatorStack into postfix string
remove '(' from operatorStack
*/
String topOfoperatorStack = (String)operatorStack.peek();
while (! topOfoperatorStack.equals("(")){
//String a=(String)operatorStack.pop();
//System.out.println(a); //for testing process
postfix+=operatorStack.pop();
topOfoperatorStack = (String) operatorStack.peek();
}
operatorStack.pop();
//String c= (String) operatorStack.pop();
//System.out.println("c: "+c); //for testing if we correctly removing (
return redundantFunction(exp);
}
else if (isOperand(ch)){
/*
if an operand a-zA-Z atau digit \\d
directly appened to infix
*/
postfix+=ch;
return redundantFunction(exp);
}
else if (isOperator(ch)){
/*
if operators
if empty
directly push into operatorStack
else
see top of operatorStack
if higher precendence
directly push into operatorStack
else
pop topOfoperatorStack
append it to postfix string
push current operator into operatorStack
*/
if (operatorStack.isEmpty()){
operatorStack.push(ch);
return redundantFunction(exp);
}
else {
String topOfoperatorStack = (String)operatorStack.peek();
if (precendence(ch) > precendence(topOfoperatorStack)){
operatorStack.push(ch);
return redundantFunction(exp);
}
else {
postfix+=(String)operatorStack.pop();
operatorStack.push(ch);
return redundantFunction(exp);
}
}
}
else{
//catching all other possible situation supposedly
return redundantFunction(exp);
}
}
}
/**toPrefix**********************************************/
private static String toPrefix(String exp){
temp="";
if (iprecendence( (String) operatorStack.peek() )) ){
operatorStack.push(ch);
}
else{
temp=CASE3();
operandStack.push(temp);
}
}
//System.out.println(ch);//testing
return redundantFunction(exp);
}
else{
while(! operatorStack.isEmpty()){
temp=CASE3();
operandStack.push(temp);
}
//System.out.println("Who is it? : "+operandStack.peek());//testing
/*if (operandStack.isEmpty())//testing
return "operandStack.isEmpty()";
else*/
return (String) operandStack.pop();
}
}
/**isOperator********************************************/
private static boolean isOperator(String ch){//method to check operator
String operators = "*/%+-";
if (operators.indexOf(ch) != -1)
return true;
else
return false;
}
/**isOperand********************************************/
private static boolean isOperand(String ch){//check if it is alphanumeric - method taken from outside sources
if (ch.matches("[a-zA-Z]|\\d"))
return true;
else
return false;
}
/**precedence********************************************/
private static int precendence(String ch){//method that check the precendence of operator and return it
//value 1 or 2
String precendence2 = "*/%";
String precendence1 = "+-";
if (precendence2.indexOf(ch) != -1)
return 2;
else if (precendence1.indexOf(ch) != -1)
return 1;
else
return 0;
}
/**redundantFunction********************************************/
private static String redundantFunction(String exp){
/*redundant processes
need i to iterate through infix string while using recursion technique
*/
i++;
if (menu==1)
return toPostfix(exp); //the recursion part
else
return toPrefix(exp); //the recursion part
}
/**reverse********************************************/
private static String reverse(String exp){
Stack tempString = new Stack();
for (int index=0;index tempString.push( exp.charAt(index) );
}
exp="";
while (! tempString.isEmpty() ){
exp+= tempString.pop();
}
return exp;
}
private static String CASE3(){
String opt="",oprn1="",oprn2="";
opt += operatorStack.pop();
oprn1 += operandStack.pop();
if (operandStack.isEmpty())
oprn2+="";
else
oprn2 += operandStack.pop();
temp=opt+oprn2+oprn1;
//System.out.println("Temp:"+temp);
return temp;
}
}
Learn More :
Arithmetic Expressions
Convert
Stack
Recursive
If the answers is incorrect or not given, you can answer the above question in the comment box. If the answers is incorrect or not given, you can answer the above question in the comment box.