Implement a calculator. For example given input ( ( ( 1 + 5 ) / ( sqrt 100 ) ) * 2 ), the out put should be 1.2.
Solution: We can use 2 stacks to parse the expression, if the expression has N symbols, the time complexity is O(N), the space complexity is O(N).
import java.util.Stack;
import java.lang.Math;
public class Calculator {
public static Double calculate(String expression) {
Stack<String> ops = new Stack<>();
Stack<Double> vals = new Stack<>();
for(String i : expression.split(" ")) {
if(i.equals("(")) {
//do nothing
} else if(i.equals("+") || i.equals("-") || i.equals("*") || i.equals("/") || i.equals("sqrt")) {
ops.push(i);
} else if(i.equals(")")) {
Double v = vals.pop();
String op = ops.pop();
if(op.equals("+")) v = vals.pop() + v;
else if(op.equals("-")) v = vals.pop() - v;
else if(op.equals("*")) v = vals.pop() * v;
else if(op.equals("/")) v = vals.pop() / v;
else if(op.equals("sqrt")) v = Math.sqrt(v);
vals.push(v);
} else {
vals.push(Double.parseDouble(i));
}
}
return vals.pop();
}
public static void main(String[] args) {
String expr = "( ( ( 1 + 5 ) / ( sqrt 100 ) ) * 2 )";
System.out.println(expr + " = " + calculate(expr));
}
}
