1+ // 224. 基本计算器
2+
3+
4+ /*
5+ 双栈：
6+ 1、使用两个栈，numsStack 存放数字，opsStack 存放操作符
7+ 2、预处理：
8+ 1）由于第一个数可能是负数，为了减少边界判断，先往 numsStack 添加一个 0
9+ 2）输入中不存在两个连续的操作符，为防止 () 内出现的首个字符为运算符，将所有空格去掉，将 (- 替换为 (0- ，(+ 替换为 (0+
10+ 3、遍历字符串中的字符
11+ 1）遇到 ( 时，则存入操作符栈
12+ 2）遇到 ) 时，
13+ ① 当操作符栈 不为空 且 栈顶不是左括号时，取出两个数字和操作符进行计算，并将计算结果存入数字栈
14+ ② 直到遇到左括号，从操作符栈 出栈
15+ 3）遇到数字时，继续遍历获取连续的数字，并将字符串转化成整型类型数字，最后数字存入数字栈
16+ 4）遇到操作符 +、- 时，
17+ ① 如果前一字符是左括号，要先将0存入数字栈，表示 (0- 或 (0+ ，才能进行计算
18+ ② 当操作符栈 不为空 且 栈顶不是左括号时，取出两个数字和操作符进行计算，并将计算结果存入数字栈
19+ ③ 将当前操作符存入 操作符栈
20+ 4、操作符栈仍不为空时，取出两个数字和操作符进行计算，并将计算结果存入数字栈，最终返回数字栈顶值
21+ 5、计算的时机：
22+ 1）当前字符为 ) ，操作符栈顶字符为 (，说明括号内的数字计算完了，可以结束了
23+ 当前字符为 +、- ，操作符栈顶字符为 (，说明括号内的数字只有一个，还不能计算
24+ 所以遇到 )、+、- 时，操作符栈 不为空 且 栈顶不是 ( 时才能计算
25+ 2）遇到 )、+、- 时，才会计算前一操作符的结果，然后将 (出操作符栈 或 +、-入操作符栈
26+ 3）字符串遍历完后，操作符栈会不为空，因为 遇到新的操作符才会计算旧的操作符 和 受到(的限制 导致前面的没有计算，但只剩 +、-，所以可以直接计算
27+ */
28+ class Solution {
29+ public int calculate (String s ) {
30+ Deque <Character > opsStack = new ArrayDeque <>();
31+ Deque <Integer > numsStack = new ArrayDeque <>();
32+ numsStack .push (0 );
33+ s = s .replaceAll (" " , "" );
34+ int n = s .length ();
35+ char [] charArray = s .toCharArray ();
36+ for (int i = 0 ; i < n ; i ++) {
37+ char c = charArray [i ];
38+ if (c == '(' ) {
39+ opsStack .push (c );
40+ } else if (c == ')' ) {
41+ while (!opsStack .isEmpty () && opsStack .peek () != '(' ) {
42+ cal (numsStack , opsStack );
43+ }
44+ opsStack .pop ();
45+ } else if (Character .isDigit (c )) {
46+ int j = i , num = 0 ;
47+ while (j < n && Character .isDigit (charArray [j ])) {
48+ num = num * 10 + charArray [j ++] - '0' ;
49+ }
50+ numsStack .push (num );
51+ i = j - 1 ;
52+ } else {
53+ if (i > 0 && charArray [i - 1 ] == '(' ) {
54+ numsStack .push (0 );
55+ }
56+ while (!opsStack .isEmpty () && opsStack .peek () != '(' ) {
57+ cal (numsStack , opsStack );
58+ }
59+ opsStack .push (c );
60+ }
61+ }
62+ while (!opsStack .isEmpty ()) {
63+ cal (numsStack , opsStack );
64+ }
65+ return numsStack .peek ();
66+ }
67+
68+ private void cal (Deque <Integer > numsStack , Deque <Character > opsStack ) {
69+ if (numsStack .isEmpty () || numsStack .size () < 2 || opsStack .isEmpty ()) {
70+ return ;
71+ }
72+ int b = numsStack .pop (), a = numsStack .pop ();
73+ char op = opsStack .pop ();
74+ numsStack .push (op == '+' ? a + b : a - b );
75+ }
76+ }
77+
78+
79+ /*
80+ ArrayDeque使用不同的api
81+ */
82+ class Solution {
83+ public int calculate (String s ) {
84+ Deque <Character > opsQueue = new ArrayDeque <>();
85+ Deque <Integer > numsQueue = new ArrayDeque <>();
86+ numsQueue .addLast (0 );
87+ s = s .replaceAll (" " , "" );
88+ int n = s .length ();
89+ char [] charArray = s .toCharArray ();
90+ for (int i = 0 ; i < n ; i ++) {
91+ char c = charArray [i ];
92+ if (c == '(' ) {
93+ opsQueue .addLast (c );
94+ } else if (c == ')' ) {
95+ while (!opsQueue .isEmpty () && opsQueue .peekLast () != '(' ) {
96+ cal (numsQueue , opsQueue );
97+ }
98+ opsQueue .pollLast ();
99+ } else if (Character .isDigit (c )) {
100+ int j = i , num = 0 ;
101+ while (j < n && Character .isDigit (charArray [j ])) {
102+ num = num * 10 + charArray [j ++] - '0' ;
103+ }
104+ numsQueue .addLast (num );
105+ i = j - 1 ;
106+ } else {
107+ if (i > 0 && charArray [i - 1 ] == '(' ) {
108+ numsQueue .addLast (0 );
109+ }
110+ while (!opsQueue .isEmpty () && opsQueue .peekLast () != '(' ) {
111+ cal (numsQueue , opsQueue );
112+ }
113+ opsQueue .addLast (c );
114+ }
115+ }
116+ while (!opsQueue .isEmpty ()) {
117+ cal (numsQueue , opsQueue );
118+ }
119+ return numsQueue .peekLast ();
120+ }
121+
122+ private void cal (Deque <Integer > numsQueue , Deque <Character > opsQueue ) {
123+ if (numsQueue .isEmpty () || numsQueue .size () < 2 || opsQueue .isEmpty ()) {
124+ return ;
125+ }
126+ int b = numsQueue .pollLast (), a = numsQueue .pollLast ();
127+ char op = opsQueue .pollLast ();
128+ numsQueue .addLast (op == '+' ? a + b : a - b );
129+ }
130+ }
0 commit comments