1 import java.util.Scanner;
2 import java.util.Stack;
3
4 /**
5 This program evaluates arithmetic expressions, using two stacks.
6 */
7 public class ExpressionCalculator
8 {
9 public static void main(String[] args)
10 {
11 Scanner in = new Scanner(System.in);
12 System.out.print("Enter an expression: ");
13 String expression = in.nextLine().replace(" ", "");
14
15 Stack<Integer> numstack = new Stack<Integer>();
16 Stack<Character> opstack = new Stack<Character>();
17
18 int pos = 0;
19 while (pos < expression.length())
20 {
21 char ch = expression.charAt(pos);
22 pos++;
23 if (isOperator(ch))
24 {
25 if (opstack.size() == 0) { opstack.push(ch); }
26 else
27 {
28 char oldOp = opstack.pop();
29 if (precedence(ch) > precedence(oldOp)) { opstack.push(oldOp); }
30 else { evaluateTop(numstack, oldOp); }
31 opstack.push(ch);
32 }
33 }
34 else if (ch == '(') { opstack.push(ch); }
35 else if (ch == ')')
36 {
37 boolean done = false;
38 while (!done)
39 {
40 if (opstack.size() == 0) { error("No matching ("); }
41 char oldOp = opstack.pop();
42 if (oldOp == '(') { done = true; }
43 else { evaluateTop(numstack, oldOp); }
44 }
45 }
46 else if (Character.isDigit(ch))
47 {
48 int start = pos - 1;
49 while (pos < expression.length()
50 && Character.isDigit(expression.charAt(pos))) { pos++; }
51 String num = expression.substring(start, pos);
52 numstack.push(Integer.parseInt(num));
53 }
54 else { error ("Number, operator, or parenthesis expected."); }
55 }
56 while (opstack.size() > 0)
57 {
58 char oldOp = opstack.pop();
59 if (oldOp == '(') { error("No matching )"); }
60 else { evaluateTop(numstack, oldOp); }
61 }
62 if (numstack.size() == 0) { error("Syntax error"); }
63 System.out.println(numstack.pop());
64 if (numstack.size() > 0) { error("Syntax error"); }
65 }
66
67 /**
68 Tests if a token is an operator.
69 @param s the token
70 @return true if s is one of: + - * / ^
71 */
72 public static boolean isOperator(char ch)
73 {
74 return ch == '+' || ch == '-' || ch == '*' || ch == '/';
75 }
76
77 /**
78 Prints an error message and exits.
79 @param message information about the error
80 */
81 public static void error(String message)
82 {
83 System.out.println("ERROR: " + message + ".");
84 System.exit(1);
85 }
86
87 /**
88 Computes the precedence level of an operator.
89 @param s the operator
90 @return the precedence level (1 = lowest, 3 = highest)
91 */
92 public static int precedence(char ch)
93 {
94 if (ch == '+' || ch == '-') { return 1; }
95 else if (ch == '*' || ch == '/') { return 2; }
96 else { return 0; }
97 }
98
99 /**
100 Computes a new value and pushes it on the stack.
101 @param num the stack for the operands and result
102 @param op the operation to use
103 */
104 public static void evaluateTop(Stack<Integer> num, char op)
105 {
106 if (num.size() == 0) { error("Syntax error"); }
107 int y = num.pop();
108 if (num.size() == 0) { error("Syntax error"); }
109 int x = num.pop();
110 int z = 0;
111 if (op == '*') { z = x * y; }
112 else if (op == '/')
113 {
114 if (y == 0) { error("Divide by 0"); }
115 else { z = x / y; }
116 }
117 else if (op == '+') { z = x + y; }
118 else if (op == '-') { z = x - y; }
119 else { error("Syntax error"); }
120 num.push(z);
121 }
122 }