-
Notifications
You must be signed in to change notification settings - Fork 27
Expand file tree
/
Copy pathReversePolishNotation.java
More file actions
171 lines (158 loc) · 5.11 KB
/
Copy pathReversePolishNotation.java
File metadata and controls
171 lines (158 loc) · 5.11 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
160
161
162
163
164
165
166
167
168
169
170
171
package hard;
import java.util.Stack;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
/**
* Have the function ReversePolishNotation(str) read str which will be an arithmetic expression
* composed of only integers and the operators: +,-,* and /
* and the input expression will be in postfix notation (Reverse Polish notation),
* an example: (1 + 2) * 3 would be 1 2 + 3 * in postfix notation.
* Your program should determine the answer for the given postfix expression.
* For example: if str is 2 12 + 7 / then your program should output 2.
*/
class ReversePolishNotation {
private static final Stack<String> stack = new Stack<>();
/**
* Cleaning, parsing and splitting the input string into the array of tokens.
* 1. convert to lowercase
* 2. remove multiple spaces
* 3. split two bundled characters (but only when the second character is not a digit)
* 4. split bundled command/operator and a digit. Excl. minus to keep negative numbers intact.
* 5. trim (remove leading and trailing spaces)
* 6. split to array of strings
*
* @param input input string
* @return String array with parsed operators and operands
*/
private static String[] parseConsoleInput(String input) {
return input
.toLowerCase()
.replaceAll(" +", " ")
.replaceAll("([\\p{P}\\p{S}a-z0-9])(?=[\\p{P}\\p{S}a-z])", "$1 ")
.replaceAll("([^- 0-9])(?=[0-9])", "$1 ")
.trim()
.split(" ");
}
/**
* Prints out a message to the console if the user input is invalid.
*
* @param op single element of the input string
*/
private static void printInputError(String op) {
System.out.println("Unrecognised operator or operand: \"" + op + "\".");
}
/**
* Reduces two operands to a single result
* by performing an arithmetical operation.
*
* @param a operand A
* @param b operand B
* @param operator denotes operation type (addition, substraction, division etc.)
* @return result of the arithmetical operation
* @throws ArithmeticException if divisor is 0
*/
public static long reduceOperands(long a, long b, String operator) {
switch (operator) {
case "+":
return a + b;
case "-":
return a - b;
case "*":
return a * b;
case "/":
if (b == 0) {
System.out.println("Divide by 0.");
throw new ArithmeticException();
}
return a / b;
default:
return 0;
}
}
/**
* Checks if the token is an operand (0-9).
*
* @param op a single token from the input string
* @return true if the token is an operand, false if not
*/
private static boolean isOperand(String op) {
Pattern pattern = Pattern.compile("^[\\d]|^-[\\d]");
Matcher matcher = pattern.matcher(op);
return matcher.find();
}
/**
* Checks if the token is an operator + - * / : ^ ( ) etc.
*
* @param op a single token from the input string
* @return true if the token is an operator, false if not
*/
private static boolean isOperator(String op) {
Pattern pattern = Pattern.compile("^[+\\-*/^%]");
Matcher matcher = pattern.matcher(op);
return matcher.find();
}
/**
* Takes two operands from stack and perform the operation with a provider operator.
*
* @param operator denotes operation type (addition, substraction, division etc.)
* @return result of the evaluation
*/
private static String performArithOperation(String operator) {
if (stack.size() >= 2) {
// Safe to evaluate
String elementB = stack.pop();
String elementA = stack.pop();
long opB = Long.parseLong(elementB);
long opA = Long.parseLong(elementA);
long result = reduceOperands(opA, opB, operator);
return Long.toString(result);
} else {
// Stack underflow since at least one element is null
return null;
}
}
/**
* Computes the entire expression in Reverse Polish Notation.
*
* @param tokens expression tokens that are already parsed and split to Array of Strings
*/
private static Long evaluateExpression(String[] tokens) {
for (String token : tokens) {
// token is an operand, push it to stack and move on
if (isOperand(token)) {
stack.push(token);
continue;
}
// token is an operator, evaluate
if (isOperator(token)) {
String result = performArithOperation(token);
if (result != null) {
stack.push(result);
}
continue;
}
// token is illegal
printInputError(token);
}
// all tokens have been processed
if (stack.isEmpty()) {
return null;
}
return Long.parseLong(stack.peek());
}
public static String reversePolishNotation(String expression) {
String[] tokens = parseConsoleInput(expression);
Long result = evaluateExpression(tokens);
return result == null ? "" : result.toString();
}
/**
* Entry point.
*
* @param args command line arguments
*/
public static void main(String[] args) {
String expression = "1 1 + 1 + 1 +";
String result = reversePolishNotation(expression);
System.out.println(result);
}
}