This algorithm is a way of evaluating fully parenthesised equations (e.g. (1+((2+3)*(4*5)))). It does this by pushing operands and operators to the stack whilst ignoring left brackets "(". Upon encountering a right bracket ")", it pops two operands and one operator, and calculates them accordingly.
It must be noted that fully parenthesised equations include only two operands and one operator for every set of parenthesis -- this algorithm wouldn't work if it used something like (1+2*3).
public class Evaluate {
public static void main(String[] args) {
Stack<String> ops = new Stack<String>();
Stack<Double> vals = new Stack<Double>();
while (!StdIn.isEmpty()) { // Read token, push if operator.
String s = StdIn.readString();
if (s.equals("(")) ;
else if (s.equals("+")) ops.push(s);
else if (s.equals("-")) ops.push(s);
else if (s.equals("*")) ops.push(s);
else if (s.equals("/")) ops.push(s);
else if (s.equals("sqrt")) ops.push(s);
else if (s.equals(")")) { // Pop, evaluate, and push result if token is ")".
String op = ops.pop();
double v = vals.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);
} // Token not operator or paren: push double value.
else vals.push(Double.parseDouble(s));
}
StdOut.println(vals.pop());
}
}