Repository navigation
Expand file tree
/
Copy pathPolishNotation.java
More file actions
150 lines (128 loc) · 13.1 KB
/
Copy pathPolishNotation.java
File metadata and controls
150 lines (128 loc) · 13.1 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
import java.util.ArrayList;
public class PolishNotation {
public static void main(String[] args)
{
// String[] tokens = {"2", "1", "+", "3", "*"};
// System.out.println(evalRPN(tokens));
// String[] tokens2 = {"4", "13", "5", "/", "+"};
// String[] tokens2 = {"10","6","9","3","+","-11","*","/","*","17","+","5","+"};
// System.out.println(evalRPN(tokens2));
String[] tokens2 = {"-20","36","-","9","12","+","-6","-","15","-","+","16","+","35","+","39","+","29","-","36","34","39","-","-","-","2","-","13","-3","+","/","29","+","2","+","36","39","-","-","37","+","-6","+","-13","-","-13","-","27","+","-5","+","22","-11","25","+","-","-","18","-","37","-3","-6","-19","+","14","+","+","+","+","4","-","20","+","17","+","28","-","25","-","7","-","-1","-17","-10","11","-","-","-","17","+","+","26","-","33","-","4","-","30","+","29","-","23","-","-12","4","-14","-","*","-","37","6","+","-13","-18","-15","-","-","-","+","17","-","-20","+","14","+","0","+","17","+","18","+","-16","37","-","-","24","3","+","-","-18","-","34","-","15","-","2","+","-13","-","-19","35","1","-","+","-4","-","-","10","22","4","-","-","-8","-","*","26","+","-10","18","+","18","-","+","1","+","14","-","25","+","1","+","3","12","+","+","-15","-11","+","-6","-3","+","-","39","+","+","-13","-","-2","38","-","-12","+","+","17","-","1","-","1","-","28","+","24","-20","-17","+","-","37","+","21","-18","-14","15","-15","-","+","-","-11","+","0","+","0","+","-12","+","13","-","+","-","-","-8","10","/","+","-6","9","5","+","+","10","+","-18","+","+","13","+","23","-","35","-","-8","+","20","+","-20","+","-9","-","37","-","28","-18","-","-","-7","-","-8","-","30","+","-1","20","-","4","-","-","17","+","21","+","-4","+","39","-2","+","+","-8","-","-1","1","+","-","39","+","34","+","15","5","-","-","2","+","-11","+","25","30","+","-","33","-","38","-","25","-","24","24","25","22","-","-","+","-14","+","*","15","+","9","+","14","-","-17","12","-","20","+","-","-16","-","10","-","-3","+","39","10","-","0","15","+","14","16","-15","+","-","-","-","-15","+","-5","-","+","26","+","-20","-","21","3","+","8","+","10","13","4","34","-","+","21","30","+","+","+","+","15","-","-","39","+","36","-","11","-","-15","6","-12","-8","-","9","+","-16","-","+","+","+","-13","36","14","31","21","+","-13","29","10","-2","21","-","+","-20","-","17","-","30","-20","4","-","12","29","-","-","+","-","+","+","+","28","-","-","34","+","36","+","-","-","+","-10","34","-14","-","-11","20","-7","+","+","-","27","+","-","+","-9","+","2","-","-15","-","-14","+","9","-","15","+","14","-","24","22","+","+","9","+","39","+","34","-6","-","+","25","4","+","12","+","+","-9","+","24","-","-2","32","-","37","-7","15","-","-2","25","-","+","-","+","-","31","-18","-","+","19","-","5","-","14","-","-7","20","-20","-18","-","+","-14","-","20","-","-15","+","19","+","16","+","+","-","0","+","-7","+","23","-","3","-","33","-","29","+","-3","+","23","+","16","30","+","+","25","+","-9","8","/","+","-7","-9","-1","-","20","-","0","+","-","+","34","-","22","+","17","-17","+","+","24","-","-9","+","7","+","23","+","28","-","31","+","7","-","-6","+","16","15","-","+","6","-","1","6","+","37","+","38","+","23","-6","-18","-","-15","-","12","+","27","-","-17","-","4","+","0","13","+","+","34","+","-16","-","21","-","14","-","-","-","+","-20","-","21","-2","-5","-","-","+","32","+","12","-","20","-","-19","8","+","13","-","11","+","-4","+","+","-3","/","6","+","26","16","+","-12","12","14","-14","-","-6","+","+","-","-15","+","+","17","+","+","32","+","13","+","-9","-17","9","-","35","23","6","14","-","-","+","-","-","-1","32","-6","+","-","-","-11","12","-","-9","-","10","23","-","+","+","-","26","-","15","+","21","+","3","-","-19","+","1","-","25","/","-11","17","-","-","-16","-","-16","-","15","8","-","-13","-16","-","-","-","8","+","39","+","-11","-","12","+","4","-","39","*","-6","39","+","+","-7","-1","33","-14","-","+","21","-","30","+","+","34","+","+","18","-","-13","+","-13","-","24","-","10","+","31","-","29","-9","-","31","-","+","-16","27","+","-","10","+","3","+","3","17","-","13","37","-","36","25","+","4","8","-","36","-","21","-","-","-","-","+","19","-","1","+","-1","+","9","16","22","+","+","-12","-","-","37","33","-","-","9","-16","+","+","-1","-","30","+","35","-","18","-","34","+","13","-","-14","-","22","-","30","-12","+","+","2","-","35","+","-20","-","-10","-","15","+","21","+","-4","+","18","-","17","1","+","+","35","-3","+","9","-","-","21","+","2","+","22","+","4","-","20","25","-2","-","-","-","16","+","4","/","36","-20","-","38","-","-","14","+","-11","-","35","+","25","-","-12","-","-14","+","17","+","1","+","11","-","-11","7","-18","39","-","11","+","28","-","-","4","-","+","35","-","7","7","-6","-","-","-","+","21","11","+","+","-7","36","+","39","7","0","+","+","-12","-3","+","+","14","-3","-","+","37","29","22","9","+","38","17","+","+","3","32","+","-3","25","-17","-4","+","6","-","+","1","-9","8","-8","-","+","+","-","-","-","32","*","+","+","-","+","18","3","14","/","-","+","+","+","-11","+","38","-","-19","-16","+","-","23","+","12","-","-2","+","-20","-15","13","0","+","+","-3","-","-","-","5","38","-","15","-","8","+","-","-2","+","14","-","8","-","6","23","-","-","20","+","23","38","25","34","+","+","-12","16","-","3","4","*","-","+","-","30","+","12","-","-","12","+","3","-","36","-12","+","+","2","1","-","-","-20","-3","-","-15","+","5","-","27","+","+","-8","+","-15","-","16","+","19","+","30","29","+","-","26","-","-1","-6","+","-","17","-7","+","+","12","-","28","-","28","2","-20","-","-16","-","-","8","4","5","-","-","-3","4","+","-","34","20","38","-","+","-","+","-","-12","-3","13","-","-20","-","+","-9","10","-","38","+","-17","-11","-6","-","37","+","+","+","-","8","-","+","14","+","3","+","26","-","19","+","-7","+","30","-","7","17","-","15","-","+","-4","-","21","+","19","7","-","+","-9","-","-19","+","38","-","13","-","-6","+","32","-","31","-","-10","23","-","25","-","-9","-","-11","2","+","2","-","-19","+","+","+","15","-13","10","17","-","-","+","-","11","-15","+","+","-1","-","31","-12","+","-11","-","+","-3","+","-16","-8","+","-","17","16","-","+","32","-","-3","-","3","-","0","-","-20","-","7","-3","4","13","+","15","-16","+","+","+","-1","-","+","+","4","-","8","/","12","+","-18","-","18","21","-","-","-10","+","-13","+","12","-20","-","-","2","-","3","-","25","-12","+","-","1","-","-12","16","+","-","23","+","30","-10","-","10","+","20","-","-","13","+","6","-8","+","-","34","35","-","-12","+","-","38","+","-15","+","8","-","25","16","24","-","34","-","4","0","16","10","-2","+","+","+","+","+","-","-2","+","-","17","-","37","19","-","38","+","35","-8","-","-12","9","-10","+","+","-","+","-","11","-","7","27","+","-10","-","+","-14","+","4","-","7","24","-","-3","-","37","-","13","-","-","39","+","9","24","22","-15","+","+","0","9","23","-","+","25","+","25","-","-","+","+","-4","+","-6","-","-12","-","16","1","+","+","0","-","3","-13","-14","-","+","+","15","-","-5","12","+","-","-4","-","39","+","2","11","-16","-","-","+","29","+","-17","24","-16","-","30","11","+","+","+","28","+","29","6","37","+","30","28","+","-10","-","+","17","+","-","-","-","3","-","10","+","37","-","-2","8","+","+","-7","+","21","+","11","+","-1","-1","-","+","11","-","-18","31","38","+","+","5","+","-","-14","-19","-","19","23","-","28","*","-","+","-16","-12","-","-17","35","-","+","-","1","+","-4","-","-19","+","-15","-","14","-","13","-","-11","-10","19","-","35","+","+","-","39","-","22","-3","+","+","24","+","-2","28","-","-","32","-","34","+","-3","+","36","-","17","-","-14","-","28","10","-","-","13","-3","+","-20","-","+","-11","+","0","+","10","+","-3","-","-4","-8","-","+","6","+","14","+","-14","2","+","14","-","-","19","+","3","-","1","-18","-","8","+","+","30","+","13","1","+","+","19","-","1","+","36","26","-","15","11","+","-11","+","+","-18","6","-6","+","-","-13","+","36","+","28","+","-","+","30","-13","+","0","-","+","21","+","33","+","5","3","+","14","+","31","-","35","+","+","-7","-","35","-6","+","+","29","14","39","+","18","-","-","14","+","-14","2","27","-","+","12","+","+","24","-14","-","-","-17","8","-","-","35","13","-11","25","24","19","-","22","-","+","+","3","+","-7","-","+","-","10","-","7","+","-","-","24","+","18","-","25","-","35","-12","+","25","29","-","3","-","-","-","15","22","-","11","-","-","9","25","-","-","-9","+","-15","-","-15","-","-16","-5","+","+","-1","+","22","39","-7","-5","-","-","-","-","25","+","-15","+","28","-","20","0","-","-","-12","-","18","-","10","+","0","+","16","-","29","-","15","+","24","-","3","7","-","0","36","30","-16","-","32","+","+","39","10","-","19","31","-","-5","+","1","+","+","+","6","1","-","+","-12","-2","-6","17","-","31","+","-3","/","28","-","+","14","+","29","6","-","20","19","26","-","-","12","-","5","28","-","18","25","11","0","29","-","+","-13","+","-","-","-","-","-","-","-","-16","+","-6","-11","-3","-","+","-","+","-","+","+","2","1","-","-","28","+","24","+","3","-","6","11","-8","-","-16","15","+","-","-","+","31","+","-3","-","6","-","14","-20","-","0","-","-13","29","-18","-","+","38","+","-","-1","-","+","-1","-","-5","33","16","+","+","-","-20","2","+","-18","+","22","-","-20","-","-","12","37","-","+","30","18","+","+","33","31","-","20","-","-","-6","-","-11","+","1","18","+","34","-","+","28","9","-","32","23","28","-","+","-6","-20","-","+","-4","26","+","-","-","-","-17","-","3","+","-1","+","-19","+","3","9","+","26","+","+","21","+","22","-","1","-","6","+","23","-","4","-","17","25","+","-17","-","+","20","21","-","18","34","-13","+","-","-","38","19","-","+","-","35","+","22","3","+","-","23","18","-9","+","6","-17","-","+","32","-3","+","+","+","-","5","2","14","+","+","-","34","22","-","+","7","+","-20","+","-13","-","36","-","4","+","17","-","26","+","33","-","-12","+","21","-","-11","+","-2","-","-15","-","18","+","14","-","-18","+","6","+","11","-","25","32","-","*"};
System.out.println(evalRPN(tokens2));
}
public static int evalRPN(String[] tokens)
{
// add all tokens to arraylist for easy manipulation
ArrayList<String> list = new ArrayList<String>();
for(int i = 0; i < tokens.length; i++)
list.add(tokens[i]);
// while there is not an answer (size = 1), find triples and do calculations
while(list.size() != 1)
findTrip(list, 0);
return Integer.parseInt(list.get(0));
}
private static void findTrip(ArrayList<String> list, int i) {
//
// System.out.println("Index " + i);
// System.out.println(list.get(i) + " " + list.get(i+1) + " " + list.get(i+2));
// System.out.println();
// for(int m = 0; m < list.size(); m++)
// System.out.print(list.get(m) + " ");
// System.out.println();
// System.out.println();
// Find trips int, int, arithmetic_operation
// make sure the 3rd item is an arithmetic operation
// else move over 1 and find a trip
// and then return so we can parse from the beginning
if(!isArithOp(list.get(i + 2)))
{
// System.out.println("Not arith " + list.get(i+2));
findTrip(list, i + 1);
return;
}
// check to see int, int are indeed ints, else go to the next one
// return so we can parse from the beginning again
int k = 0, j = 0;
try{
k = Integer.parseInt(list.get(i));
j = Integer.parseInt(list.get(i + 1));
}catch(NumberFormatException e)
{
// System.out.println("ERR " + list.get(i) + " " + list.get(i+1));
findTrip(list, i + 1);
return;
}
// System.out.println();
// for(int m = 0; m < list.size(); m++)
// System.out.print(list.get(m) + " ");
// System.out.println();
// System.out.println();
// calculate answer
int ans = arith(k, j, list.get(i+2));
// System.out.println(k + list.get(i+2) + j + " = " + ans);
// System.out.println("Removing " + list.get(i+2) + " & " + list.get(i+1));
// System.out.println("Setting " + list.get(i) + " = " + ans);
// set answer to first index, and remove the next 2 indices
list.set(i, ans + "");
list.remove(i + 1);
list.remove(i + 1);
// System.out.println();
// for(int m = 0; m < list.size(); m++)
// System.out.print(list.get(m) + " ");
// System.out.println();
// System.out.println();
// System.out.println("END");
}
private static int eval(int i, int j, String a) {
return 0;
// if(list.size() == 1)
// return Integer.parseInt(list.get(0));
//
// String a = list.get(index + 2);
// String ans = "";
//
// if(isArithOp(a))
// {
// int i = 0;
// int j = 0;
// try{
// i = Integer.parseInt(list.get(index));
// j = Integer.parseInt(list.get(index + 1));
//
// }catch(NumberFormatException e)
// {
//
// }
//
// ans = arith(i, j, a) + "";
// }
// eval(list, index + 3);
// System.out.println("removing " + list.get(index+1));
// list.remove(index + 1);
// System.out.println("removing " + list.get(index));
// list.remove(index);
// System.out.println("inserting " + ans);
// list.set(0, ans);
//
// for(int i = 0; i < list.size(); i++)
// {
// System.out.print("("+i+")"+ list.get(i) + " ");
// }
// System.out.println();
// return eval(list, 0);
}
private static int arith(int x, int y, String a) {
if(a.equals("+"))
return x + y;
else if(a.equals("-"))
return x-y;
else if(a.equals("*"))
return x * y;
else if(a.equals("/"))
return x / y;
return Integer.MIN_VALUE;
}
private static boolean isArithOp(String s) {
return (s.equals("+") || s.equals("*") || s.equals("/") || s.equals("-"));
}
}