import java.util.*;
import java.util.Stack;
public class Three {
public static void main(String[] args){
Double result = Calculate.result("(3+1)+1/3+9");
System.out.println(result);
}
}
class Calculate {
public static Double result(String str) {
List<String> strList = strToStrList(str);
List<String> postList = toPostOrder(strList);
Double result = getResult(postList);
return result;
}
private static List<String> strToStrList(String str) {
List<String> strList = new ArrayList<>();
int begin=0,end=0,post=0,i=0;
for (; i < str.length(); i++) {
if (str.charAt(i) == '+' || str.charAt(i) == '-' || str.charAt(i) == '*'
|| str.charAt(i) == '/' || str.charAt(i) == '(' || str.charAt(i) == ')') {
end = i;
if (begin < end) {
strList.add(str.substring(begin, end));
strList.add(str.substring(i,i+1));
}
else {
strList.add(str.substring(i,i+1));
}
begin = i + 1;
}
}
if (!"".equals(str.substring(begin, str.length()))){
strList.add(str.substring(begin, str.length()));
}
return strList;
}
private static List<String> toPostOrder(List<String> strList) {
Stack<String> operStack = new Stack<>();
List<String> postList = new ArrayList<>();
for (int i = 0; i < strList.size(); i++) {
if (isOper(strList.get(i), i, strList)) {
if (operStack.isEmpty()) {
operStack.push(strList.get(i));
} else {
if ("(".equals(strList.get(i))) {
operStack.push(strList.get(i));
} else if (")".equals(strList.get(i))) {
while (!"(".equals(operStack.peek())) {
postList.add(operStack.pop());
}
operStack.pop();
} else {
if ("(".equals(operStack.peek())) {
operStack.push(strList.get(i));
} else {
if (!operStack.isEmpty() && getPriority(strList.get(i)) > getPriority(operStack.peek())) {
operStack.push(strList.get(i));
} else {
if (!operStack.isEmpty() && getPriority(strList.get(i)) <= getPriority(operStack.peek()) && !"(".equals(operStack.peek())){
}
while (!operStack.isEmpty() && getPriority(strList.get(i)) <= getPriority(operStack.peek()) && !"(".equals(operStack.peek())) {
postList.add(operStack.pop());
}
if (operStack.isEmpty()) {
operStack.push(strList.get(i));
} else if (getPriority(strList.get(i)) > getPriority(operStack.peek()) || "(".equals(operStack.peek())) {
operStack.push(strList.get(i));
}
}
}
}
}
} else {
if ("-".equals(strList.get(i))){
}else if (i >= 2 && "-".equals(strList.get(i - 1)) && "(".equals(strList.get(i - 2)) ) {
postList.add(strList.get(i - 1) + strList.get(i));
} else if (i == 1 && "-".equals(strList.get(i - 1))) {
postList.add(strList.get(i - 1) + strList.get(i));
} else {
postList.add(strList.get(i));
}
}
}
while (!operStack.isEmpty()) {
postList.add(operStack.pop());
}
return postList;
}
private static double getResult(List<String> postList) {
Stack<String> numStack = new Stack();
for(int i =0 ; i < postList.size(); i++) {
if (isNum(postList.get(i))) {
numStack.push(postList.get(i));
} else if (isOper(postList.get(i), i, postList)) {
if ("+".equals(postList.get(i))) {
Double num2 = Double.parseDouble(numStack.pop());
Double num1 = Double.parseDouble(numStack.pop());
Double result = num1 + num2;
numStack.push(result.toString());
} else if ("-".equals(postList.get(i))) {
Double num2 = Double.parseDouble(numStack.pop());
Double num1;
if (numStack.isEmpty()) {
num1 = 0.0;
} else {
num1 = Double.parseDouble(numStack.pop());
}
Double result = num1 - num2;
numStack.push(result.toString());
} else if ("*".equals(postList.get(i))) {
Double num2 = Double.parseDouble(numStack.pop());
Double num1 = Double.parseDouble(numStack.pop());
Double result = num1 * num2;
numStack.push(result.toString());
} else if ("/".equals(postList.get(i))) {
Double num2 = Double.parseDouble(numStack.pop());
Double num1 = Double.parseDouble(numStack.pop());
Double result = num1 / num2;
numStack.push(result.toString());
}
}
}
return Double.parseDouble(numStack.pop());
}
private static boolean isOper(String str, int i, List<String> stringList){
if("*".equals(str)|| "/".equals(str)||
"+".equals(str)||
"(".equals(str)|| ")".equals(str)){
return true;
} else if ("-".equals(str)) {
return !(i>=1 && "(".equals(stringList.get(i-1)));
}
else{
return false;
}
}
private static boolean isNum(String str){
if("*".equals(str)|| "/".equals(str)||
"+".equals(str)|| "-".equals(str)||
"(".equals(str)|| ")".equals(str)){
return false;
}
else{
return true;
}
}
private static int getPriority(String c){
if("*".equals(c) || "/".equals(c)){
return 2;
} else if ("+".equals(c) || "-".equals(c)){
return 1;
} else {
return 999;
}
}
}