Code-Samples/converterTree.java at master · swam92/Code-Samples · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
/*converterTree uses a stack to convert standard notation to postfix notation

for example, 3+4:

3 is a number so it is appended to our currently empty postfix string.  Now postfix = 3

+ is an operator.  We check the stack and see that it is empty.  Push + onto the stack.  Postfix = 3

4 is a number so it is immediately appended to postfix.  Postfix = 3 4

At this point the entire string has been iterated through, but the stack is not empty.  We check to see that the item on the stack
is not an open parenthesis.  Its not- so we pop off the stack until it is empty and append each token to postfix.

postfix = 3 4 +


*/

package CSHomework.HW3;
import java.util.Stack;
import java.util.Scanner;

public class converterTree  {


  public static String toPostFix(String line)
  {
    int length = line.length();
    String postFix = "";
    BoundedStackInterface<String> stack = new ArrayStack<String>(length);	//initialize stack

    for(int i = 0; i < length; i++){						//iterate through infix

      char value = line.charAt(i);						//tokenize
      String s3 = Character.toString(value);

         if(value  >= '0' & value<= '9'){					//if the token is a number

               postFix = postFix + value;					//add it to postfix
	       postFix = postFix + " ";
            }

         else if("(".equals(s3)){						//if there is an open parenthesis

             String s1 = Character.toString(value);				//push on to stack for future use
             stack.push(s1);
           }


           else if(")".equals(s3)){						//if there is a closing parenthesis

             while(!("(".equals(stack.top()))){					//until the open open parenthesis

               String x = stack.top();						//append stack contents to postfix
               stack.pop();
               postFix = postFix + x;
               postFix = postFix + " ";

             }

           }

         else if(value=='+' || value=='-' || value=='*' || value=='/' || value=='^'){//if the token is an operator

             String s2 = Character.toString(value);				     //current token is named s2

             if(stack.isEmpty()){						     //if there is nothing on the stack
               stack.push(s2);							     //immediately push operator
              }

             else if(checkPrecedence(stack.top()) <= checkPrecedence(s2)){	     //if the current token has higher
               stack.push(s2);							     //precedence than the top of the
             }									     //stack push it on the stack

             else if(checkPrecedence(stack.top()) > checkPrecedence(s2)){	     //if the current token has lower precdence

               while(!(stack.isEmpty())){					     //while there are still tokens on stack

                 if("(".equals(stack.top())){					     //stop popping after you reach an open parenthesis
                 								     //we do not use parenthesis in postfix so it is not appended to postfix notation
                   stack.pop();
                   break;

                  }

                 if(checkPrecedence(stack.top()) > checkPrecedence(s2)){	     //if the top of stack has higher precedence

                   String r = stack.top();					     //append token at top of stack to postfix
                   stack.pop();
                   postFix = postFix + r;
                   postFix = postFix + " ";

                   }

               break;

             }
        stack.push(s2);								   // after previous 2 conditionals push the current token on stack
             }
         }
  }
            while(!(stack.isEmpty())){						   //empty the remaining stack contents

      		if("(".equals(stack.top())){					   //if the only thing left is an open parenthesis
      										   //pop it off stack.

              		stack.pop();
              	}

      		else{								//append all remaining items that are
      										//not parenthesis to postfix
        	String g = stack.top();
      		stack.pop();
      		postFix = postFix + g;
      		postFix = postFix + " ";

      		}
      	}
            return postFix;
  }
  /* This function assigns each operator a number based on order of operations rules.  The number value of each operator
     is used to determine when to push and pop tokens off the stack */

     public static int checkPrecedence(String value)
      {
       if("^".equals(value)){
         return 4;}
       if("*".equals(value)){
         return 3;}
       if("/".equals(value)){
         return 2;}
       if("+".equals(value)){
         return 1;}
       if("-".equals(value)){
         return 1;}
       return 0;
      }

}