-
Notifications
You must be signed in to change notification settings - Fork 96
Expand file tree
/
Copy pathBasicCalculatorII.java
More file actions
116 lines (104 loc) · 2.89 KB
/
Copy pathBasicCalculatorII.java
File metadata and controls
116 lines (104 loc) · 2.89 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
package stack;
import static org.junit.Assert.assertEquals;
import java.util.Stack;
import org.junit.Test;
/**
Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.
You may assume that the given expression is always valid.
Some examples:
"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5
Note: Do not use the eval built-in library function.
*/
public class BasicCalculatorII
{
@Test
public void test()
{
assertEquals( 7, calculate("3 + 2*2") );
assertEquals( 1, calculate("3/2") );
assertEquals( 5, calculate("3+5/2") );
assertEquals( 5, calculate("100/10/2") );
assertEquals( 2, calculate("10000000/1/2/3/4/5/6/7/8/9/10") );
assertEquals( -24, calculate("1*2-3/4+5*6-7*8+9/10"));
}
public int calculate( String s )
{
if ( s == null
|| s.length() == 0 )
{
throw new IllegalArgumentException("");
}
// assertions on validity
Stack<Integer> valStack = new Stack<>();
Stack<Character> opStack = new Stack<>();
for ( int i = 0; i < s.length( ); i++ )
{
char token = s.charAt( i );
if ( token == ' ' )
{
continue;
}
else if ( token == '(' )
{
opStack.push( token );
}
else if ( token == ')' )
{
while ( opStack.peek() != '(' )
{
valStack.push( calc( opStack.pop(), valStack.pop(), valStack.pop() ) );
}
opStack.pop();
}
else if ( Character.isDigit( token ) )
{
int start = i;
while ( i + 1 < s.length() && Character.isDigit( s.charAt( i + 1 ) ) )
{
i++;
}
valStack.push( Integer.parseInt( s.substring( start, i + 1 ) ) );
}
else
{
while ( !opStack.isEmpty() && isLowerPrece( token, opStack.peek() ) )
{
valStack.push( calc( opStack.pop(), valStack.pop(), valStack.pop() ) );
}
opStack.push( token );
}
}
while ( !opStack.isEmpty( ) )
{
valStack.push( calc( opStack.pop(), valStack.pop(), valStack.pop() ) );
}
return valStack.pop();
}
private boolean isLowerPrece( char curr, char toBeCompared )
{
return ( toBeCompared == '*' || toBeCompared == '/' )
|| ( toBeCompared == '-' && ( curr == '+' || curr == '-' ) );
}
private int calc( char operator, int operand1, int operand2 )
{
if ( operator == '+' )
{
return operand2 + operand1;
}
else if ( operator == '-' )
{
return operand2 - operand1;
}
else if ( operator == '*' )
{
return operand2 * operand1;
}
else
{
return operand2 / operand1;
}
}
}