/
P4_6EvalExpression.java
140 lines (118 loc) · 4.5 KB
/
P4_6EvalExpression.java
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
//Program P4.6
import java.io.*;
public class P4_6EvalExpression {
public static void main(String[] args) throws IOException {
char[] post = new char[255];
int n = readConvert(post);
printPostfix(post, n);
System.out.printf("\nIts value is %d\n", eval(post, n));
} //end main
public static int readConvert(char[] post) throws IOException {
//Read the expression and convert to postfix. Return the size of postfix.
Stack S = new Stack();
int h = 0;
char c;
System.out.printf("Type an infix expression and press Enter\n");
char token = getToken();
while (token != '\0') {
if (Character.isDigit(token)) post[h++] = token;
else if (token == '(') S.push(new NodeData('('));
else if (token == ')')
while ((c = S.pop().getCharData()) != '(') post[h++] = c;
else {
while (!S.empty() &&
precedence(S.peek().getCharData()) >= precedence(token))
post[h++] = S.pop().getCharData();
S.push(new NodeData(token));
}
token = getToken();
}
while (!S.empty()) post[h++] = S.pop().getCharData();
return h;
} //end readConvert
public static void printPostfix(char[] post, int n) {
System.out.printf("\nThe postfix form is \n");
for (int h = 0; h < n; h++) System.out.printf("%c ", post[h]);
System.out.printf("\n");
} //end printPostfix
public static char getToken() throws IOException {
int n;
while ((n = System.in.read()) == ' ') ; //read over blanks
if (n == '\r') return '\0';
return (char) n;
} //end getToken
public static int precedence(char c) {
//Returns the precedence of the given operator
if (c == '(') return 0;
if (c == '+' || c == '-') return 3;
if (c == '*' || c == '/') return 5;
return -99; //error
} //end precedence
public static int eval(char[] post, int n) {
//Given the postfix form of an expression, returns its value
int a, b, c;
Stack S = new Stack();
for (int h = 0; h < n; h++) {
if (Character.isDigit(post[h]))
S.push(new NodeData(post[h] - '0'));
else {
b = S.pop().getIntData();
a = S.pop().getIntData();
if (post[h] == '+') c = a + b;
else if (post[h] == '-') c = a - b;
else if (post[h] == '*') c = a * b;
else c = a / b;
S.push(new NodeData(c));
}
}
return S.pop().getIntData();
} //end eval
} //end class P4_6EvalExpression
class NodeData {
char ch;
int num;
public NodeData(char c) {
ch = c;
}
public NodeData(int n) {
num = n;
}
public NodeData(char c, int n) {
ch = c;
num = n;
}
public char getCharData() {return ch;}
public int getIntData() {return num;}
public static NodeData getRogueValue() {
return new NodeData('$', -999999);
}
} //end class NodeData
class Node {
NodeData data;
Node next;
public Node(NodeData d) {
data = d;
next = null;
}
} //end class Node
class Stack {
Node top = null;
public boolean empty() {
return top == null;
}
public void push(NodeData nd) {
Node p = new Node(nd);
p.next = top;
top = p;
} //end push
public NodeData pop() {
if (this.empty())return NodeData.getRogueValue();
NodeData hold = top.data;
top = top.next;
return hold;
} //end pop
public NodeData peek() {
if (!this.empty()) return top.data;
return null;
} //end peek
} //end class Stack