LeetCode 227 基本计算器 II （Basic Calculator II）
题目的?数：1704
题目的?数：292
1、题目描述
实现一个基本的计算器来计算一个简单的字符串表达式的值。字符串表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格 。 整数除法仅保留整数部分。示例 1:输入: "3+2*2"
输出: 7
示例 2:输入: " 3/2 "
输出: 1
示例 3:输入: " 3+5 / 2 "
输出: 5
2、思路与方法
这种计算器问题大多数都是用栈来解决，大部分题解利用的也是栈，不过这个题不涉及到括号的嵌套计算，其实不使用栈也是可以的，可以降低空间复杂度。
实例： 3 + 5*5/3 + 5 -3/5
比如以上例子，我们需要考虑的其实是： (3)+(5*5/3)+(5)-(3/5)，也就是说用加减法将公式分块，分别计算每一块中的结果，再穿起来即可。
通过以上分析，不难想到可以使用双指针的方式，找到每段的前后索引，然后再计算中间一部分的结果即可。此外，考虑使用两个技巧来避免边界情况的判断：
1）哨兵。 在前后加上 “0+” 和 "+0"即转化为
0+3 + 5*5/3 + 5 -3/5+0
这样可以保证每段都可以遍历到
2）在计算乘除时，遍历到的乘除号要等到下一个数字才能使用，那么如何计算第一个遍历到的数字呢？我们可以初始化
int cur = 1;//这个用于保存结果
int flagForNext = 1; //这个用来判断乘除，初始为1*某个数
这样就隐式的在前面加入了 1*(…)
三、代码
class Solution {
public int calculate(String s) {
s = "0+" + s + "+0";int length = s.length();int res = 0;int start = 1;int end = 1;System.out.println(s);while(end < length) {
char ch = s.charAt(start);int flag = ch == '+' ? 1:-1;//这个用来判断加减end = start+1;while(end < length && (s.charAt(end) != '+' && s.charAt(end) != '-')) ++end;//取出来这一段int cur = 1;int flagForNext = 1; //这个用来判断乘除，初始为1*某个数while(start < end) {
//获取这一段的结果存到cur，这样我们就只需要在外循环考虑加减了start++;while(s.charAt(start) == ' ') {
++start;}int num = 0;while(start < end && s.charAt(start) >= '0' && s.charAt(start) <= '9') {
int temp = s.charAt(start) - '0';num = num * 10;num += temp;++start;}if(flagForNext == 1) cur = cur * num;else cur = cur / num;while(start < end && s.charAt(start) == ' ') {
++start;}if(start < end && s.charAt(start) == '/') flagForNext = 2;//改变他，下一轮迭代使用if(start < end && s.charAt(start) == '*') flagForNext = 1;} res += flag*cur;}return res;}
}
四、复杂度
时间复杂度：双指针一重循环，时间复杂度为O(n)
空间复杂度：减少对栈的依赖，空间复杂度为O(1)
Leetcode 224:基本计算器（Basic Calculator）224. 基本计算器
题目的?数：1718
题目的?数：141
1、问题描述
实现一个基本的计算器来计算一个简单的字符串表达式的值。字符串表达式可以包含左括号 ( ，右括号 )，加号 + ，减号 -，非负整数和空格 。示例 1:输入: "1 + 1"
输出: 2
示例 2:输入: " 2-1 + 2 "
输出: 3
示例 3:输入: "(1+(4+5+2)-3)+(6+8)"
输出: 23
2、思路与方法
这个题和上个题类似，难点有所区别。上个体主要是需要对乘除法进行计算，这个题则需要考虑到括号的影响，有了括号的嵌套，例如计算(3-(3-1))时需要先计算(3-1)，这个时候自然得借助栈来实现
- 考虑栈中记录四种东西：
数字 :如果是负数，还得将'-'即-3进栈
'(' :-1
'+' :-2
'-' :-3
- 自然是当遇见 ‘)‘时出栈，其余符号时进栈，出栈时我们需要计算到上一个’(’，然后再将计算的结果进栈
- 和上面的问题类似，使用哨兵"(" + s + ")"来保证整个s我们都会记录到
小插曲：一开始做这个题的时候想到的是负数转化成 ‘-’ 和正数的形式，方便我们用负数来表示符号，然而没有考虑到的是这种情况:
5 - (1-4)
上述的方式，括号里面出栈会使栈中变成
'5','-','-','3'
可以发现产生了两个负号，事实上如果括号嵌套进一步增加，这个负号数量也许会继续增多，因此在第一个符号出栈的时候，我们还需要一直进行出栈操作，直到栈顶不再为‘+’或者’-'为止，用flag来记录符号的变化，最终代表了这一段的结果
- 最终栈中只会剩一个正数或者一个正数加一个负号，判断栈的size做出相应的返回即可
三、代码
修改了比较多东西导致代码相对冗长，过多的判断似乎也影响了效率。
class Solution {
public int calculate(String s) {
StringBuilder sb = new StringBuilder("(" + s + ")");//用栈解决括号的嵌套问题Stack<Integer> st = new Stack<>();//栈里面需要记录四种东西：//1）数字//2）'(' :-1//3）'+' :-2//4) '-' :-3int start = 0;while(start < sb.length()) {
int ch = sb.charAt(start);if(ch == ' ') {
++start;} else if(ch >= '0' && ch <= '9') {
//获取这个数字int cur = 0;while(sb.charAt(start) >= '0' && sb.charAt(start) <= '9') {
cur = cur * 10;cur += sb.charAt(start) - '0';++start;}st.push(cur);} else {
if(ch == ')') {
//出栈，求得结果int cur = 0;while(true) {
int pre = st.pop();//记录加减if(pre == -1) break;int next = st.pop();int flag = 1;if(next == -3 || next == -2) {
flag = next == -3? -1:1;while(!st.isEmpty() && (st.peek() == -3 || st.peek() == -2)){
if(st.peek() == -3) flag*=-1;st.pop();}}cur+=pre*flag;if(next == -1) break;}if(cur < 0) st.push(-3);st.push(Math.abs(cur));}if(ch == '(') st.push(-1);if(ch == '+') st.push(-2);if(ch == '-') st.push(-3);++start;}}if(st.size() == 2) return st.peek() * -1;return st.peek();}
}
四、复杂度
时间复杂度：仍为O(n)
空间复杂度：利用了一个栈，为O(n)