forked from biblelamp/JavaExercises
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathinfix.java
More file actions
159 lines (143 loc) · 5.34 KB
/
Copy pathinfix.java
File metadata and controls
159 lines (143 loc) · 5.34 KB
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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
/**
* Book: Data Structures and Algorithms in Java, by Robert LaFore
* Chapter 4:
* infix.java
* converts infix arithmetic expressions to postfix
* to compile this code: javac infix.java
* to run this program: java InfixApp
* Examples for testing:
* A+B*C -> ABC*+
* (A+B)*C -> AB+C*
* A+B*(C-D) -> ABCD-*+
*/
import java.io.*; // for I/O
class StackX {
private int maxSize;
private char[] stackArray;
private int top;
public StackX(int s) { // constructor
maxSize = s;
stackArray = new char[maxSize];
top = -1;
}
public void push(char j) { // put item on top of stack
stackArray[++top] = j;
}
public char pop() { // take item from top of stack
return stackArray[top--];
}
public char peek() { // peek at top of stack
return stackArray[top];
}
public boolean isEmpty() { // true if stack is empty
return (top == -1);
}
public int size() { // return size
return top+1;
}
public char peekN(int n) { // return item at index n
return stackArray[n];
}
public void displayStack(String s) {
System.out.print(s);
System.out.print("Stack (bottom-->top): ");
for (int j=0; j<size(); j++) {
System.out.print(peekN(j));
System.out.print(' ');
}
System.out.println("");
}
} // end class StackX
class InToPost { // infix to postfix conversion
private StackX theStack;
private String input;
private String output = "";
public InToPost(String in) { // constructor
input = in;
int stackSize = input.length();
theStack = new StackX(stackSize);
}
public String doTrans() { // do translation to postfix
for (int j=0; j<input.length(); j++) { // for each char
char ch = input.charAt(j); // get it
theStack.displayStack("For "+ch+" "); // *diagnostic*
switch (ch) {
case '+': // it's + or -
case '-':
gotOper(ch, 1); // go pop operators
break; // (precedence 1)
case '*': // it's * or /
case '/':
gotOper(ch, 2); // go pop operators
break; // (precedence 2)
case '(': // it's a left paren
theStack.push(ch); // push it
break;
case ')': // it's a right paren
gotParen(ch); // go pop operators
break;
default: // must be an operand
output = output + ch;// write it to output
break;
}
}
while (!theStack.isEmpty()) { // pop remaining opers
theStack.displayStack("While "); // *diagnostic*
output = output + theStack.pop(); // write to output
}
theStack.displayStack("End "); // *diagnostic*
return output; // return postfix
}
public void gotOper(char opThis, int prec1) { // got operator from input
while (!theStack.isEmpty()) {
char opTop = theStack.pop();
if (opTop == '(') { // if it's a '('
theStack.push(opTop); // restore '('
break;
} else { // it's an operator
int prec2; // precedence of new op
if (opTop == '+' || opTop == '-') // find new op prec
prec2 = 1;
else
prec2 = 2;
if (prec2 < prec1) { // if prec of new op less
// than prec of old
theStack.push(opTop);// save newly-popped op
break;
} else // prec of new not less
output = output + opTop; // than prec of old
}
}
theStack.push(opThis); // push new operator
}
public void gotParen(char ch) { // got right paren from input
while (!theStack.isEmpty()) {
char chx = theStack.pop();
if (chx == '(') // if popped '('
break; // we're done
else // if popped operator
output = output + chx; // output it
}
}
}
class InfixApp {
public static void main(String[] args) throws IOException {
String input, output;
while(true) {
System.out.print("Enter infix: ");
System.out.flush();
input = getString(); // read a string from kbd
if (input.equals("")) // quit if [Enter]
break;
// make a translator
InToPost theTrans = new InToPost(input);
output = theTrans.doTrans(); // do the translation
System.out.println("Postfix is " + output + '\n');
}
}
public static String getString() throws IOException {
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
return br.readLine();
}
}