fork(51) download
  1. /* A Java program to evaluate a given expression where tokens are separated
  2.   by space.
  3.   Test Cases:
  4.   "10 + 2 * 6" ---> 22
  5.   "100 * 2 + 12" ---> 212
  6.   "100 * ( 2 + 12 )" ---> 1400
  7.   "100 * ( 2 + 12 ) / 14" ---> 100
  8. */
  9. import java.util.Stack;
  10.  
  11. class EvaluateString
  12. {
  13. public static int evaluate(String expression)
  14. {
  15. char[] tokens = expression.toCharArray();
  16.  
  17. // Stack for numbers: 'values'
  18. Stack<Integer> values = new Stack<Integer>();
  19.  
  20. // Stack for Operators: 'ops'
  21. Stack<Character> ops = new Stack<Character>();
  22.  
  23. for (int i = 0; i < tokens.length; i++)
  24. {
  25. // Current token is a whitespace, skip it
  26. if (tokens[i] == ' ')
  27. continue;
  28.  
  29. // Current token is a number, push it to stack for numbers
  30. if (tokens[i] >= '0' && tokens[i] <= '9')
  31. {
  32. StringBuffer sbuf = new StringBuffer();
  33. // There may be more than one digits in number
  34. while (i < tokens.length && tokens[i] >= '0' && tokens[i] <= '9')
  35. sbuf.append(tokens[i++]);
  36. values.push(Integer.parseInt(sbuf.toString()));
  37. }
  38.  
  39. // Current token is an opening brace, push it to 'ops'
  40. else if (tokens[i] == '(')
  41. ops.push(tokens[i]);
  42.  
  43. // Closing brace encountered, solve entire brace
  44. else if (tokens[i] == ')')
  45. {
  46. while (ops.peek() != '(')
  47. values.push(applyOp(ops.pop(), values.pop(), values.pop()));
  48. ops.pop();
  49. }
  50.  
  51. // Current token is an operator.
  52. else if (tokens[i] == '+' || tokens[i] == '-' ||
  53. tokens[i] == '*' || tokens[i] == '/')
  54. {
  55. // While top of 'ops' has same or greater precedence to current
  56. // token, which is an operator. Apply operator on top of 'ops'
  57. // to top two elements in values stack
  58. while (!ops.empty() && hasPrecedence(tokens[i], ops.peek()))
  59. values.push(applyOp(ops.pop(), values.pop(), values.pop()));
  60.  
  61. // Push current token to 'ops'.
  62. ops.push(tokens[i]);
  63. }
  64. }
  65.  
  66. // Entire expression has been parsed at this point, apply remaining
  67. // ops to remaining values
  68. while (!ops.empty())
  69. values.push(applyOp(ops.pop(), values.pop(), values.pop()));
  70.  
  71. // Top of 'values' contains result, return it
  72. return values.pop();
  73. }
  74.  
  75. // Returns true if 'op2' has higher or same precedence as 'op1',
  76. // otherwise returns false.
  77. public static boolean hasPrecedence(char op1, char op2)
  78. {
  79. if (op2 == '(' || op2 == ')')
  80. return false;
  81. if ((op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-'))
  82. return false;
  83. else
  84. return true;
  85. }
  86.  
  87. // A utility method to apply an operator 'op' on operands 'a'
  88. // and 'b'. Return the result.
  89. public static int applyOp(char op, int b, int a)
  90. {
  91. switch (op)
  92. {
  93. case '+':
  94. return a + b;
  95. case '-':
  96. return a - b;
  97. case '*':
  98. return a * b;
  99. case '/':
  100. if (b == 0)
  101. throw new
  102. UnsupportedOperationException("Cannot divide by zero");
  103. return a / b;
  104. }
  105. return 0;
  106. }
  107.  
  108. // Driver method to test above methods
  109. public static void main(String[] args)
  110. {
  111. System.out.println(EvaluateString.evaluate("10 + 2 * 6"));
  112. System.out.println(EvaluateString.evaluate("100 * 2 + 12"));
  113. System.out.println(EvaluateString.evaluate("100 * ( 2 + 12 )"));
  114. System.out.println(EvaluateString.evaluate("100 * ( 2 + 12 ) / 14"));
  115. System.out.println(EvaluateString.evaluate(" ( ( 20 - 10 ) * ( 30 - 20 ) + 10 ) * 2"));
  116. System.out.println(EvaluateString.evaluate(" ( ( 20 - 10 ) * ( 30 - 20 ) / 10 + 10 ) * 2"));
  117. }
  118. }
Success #stdin #stdout 0.06s 381248KB
stdin
Standard input is empty
stdout
22
212
1400
100
220
40