代码目的:解决表达式求值
请写一个整数计算器,支持加减乘三种运算和括号。
数据范围:0/le |s| /le 1000≤∣s∣≤100,保证计算结果始终在整型范围内
要求:空间复杂度: O(n)O(n),时间复杂度 O(n)O(n)
示例1 输入: "1+2" 返回值:3
错误代码
public int solve (String s) {
// write code here
/**
* 考虑使用三个栈
1.stack1:负责储存数据 - 和 括号
2.stack2:负责储存运算符 - 并在入栈的过程中。解决*的优先级问题
*/
// 1.实例化两个栈
Stack<String> stack1 = new Stack();
Stack<Character> stack2 = new Stack();
// Stack<Character> stack3 = new Stack(); ---------< 发现不需要
int result = 0;
String str = "";
// 3.遍历循序字符串
for(int i =0 ; i < s.length(); i++){
// 3.1 处理括号优先级
if(s.charAt(i) == '(' || s.charAt(i) == ')'){
// 3.2 先让字符串入栈
stack1.push(str);
str = "";
if(s.charAt(i) == '('){
// 将该字符入栈
stack1.push(")");
continue;
}else{
System.out.println(stack1.peek());
while(!stack1.isEmpty() && stack1.peek() != ")"){ // ------------------------< 错误位置
result = this.calculate(Integer.parseInt(stack1.pop()),Integer.parseInt(stack1.pop()),stack2.pop());
stack1.push(result + "");
}
stack1.pop();
continue;
}
}
// 3.2 整合数字
if(s.charAt(i) >= '0' && s.charAt(i) <= '9'){
str = str + s.charAt(i);
continue;
}
stack1.push(str);
str = "";
// 3.4 处理乘号优先级
if(!stack2.isEmpty() && stack2.peek() == '*'){
result = this.calculate(Integer.parseInt(stack1.pop()),Integer.parseInt(stack1.pop()),stack2.pop());
stack1.push(result + "");
stack2.pop();
}
// 3.5 处理加减乘三个元素符
stack2.push(s.charAt(i));
}
// 4.最后计算加减运算
stack1.push(str);
while(!stack2.isEmpty()){
result = this.calculate(Integer.parseInt(stack1.pop()),Integer.parseInt(stack1.pop()),stack2.pop());
stack1.push(result + "");
}
return Integer.parseInt(stack1.peek());
}
调试过程
第一轮调试:
-
上网查错误原因
– 回答 : 意思是数字格式异常,也就是说 将 String类型的 “)”转成数字格式是产生了异常
– 迷惑: 因为我没有将转格式,栈stack1中数据类型都是String类型啊 -
猜想将 “)” 和 “4” 比较时,是不是有一个自动转成数字格式的过程?
– 测试 :加上一行代码 -在main中if(")" != "4") System.out.println("问题不是出在这里")
- 测试结果 :成功打印出 "问题不是出在这里"
3.猜想是不是栈将 “4” 出栈时自动将数据类型转换
– 测试:加上代码System.out.println(stack1.peek() instanceof String);
- 测试结果:输出 true
上述测试,证明 “4” 在栈顶的时候没有进行数据转换,因此也没有涉及到 String 类型转 数字类型
第二轮调试
1.材料错误出在这句话,也就是进入了while循环,有一个类型转换result = this.calculate(Integer.parseInt(stack1.pop()),Integer.parseInt(stack1.pop()),stack2.pop());
-验证猜想:在这句话上面加一段代码System.out.println("错误出在这里" + stack1.peek());
- 验证结果(输入s = `"(3+4)*(5+(2-3))"`):输出了
错误出在这里4
错误出在这里7
### 证明了问题的确出在这里,因为理论上不可能打印出 “错误出在这里7”
解决过程
1.弄清楚为什么会出现 “错误出在这里7”
- 答案:因为当时栈顶元素的确是 7 ,其下一个元素才是 ")" , 因此导致了错误
2.解决方案:修改代码如下
while(!stack1.isEmpty()){
System.out.println("错误出在这里" + stack1.peek());
result = this.calculate(Integer.parseInt(stack1.pop()),Integer.parseInt(stack1.pop()),stack2.pop());
if(stack1.peek() == ")"){
stack1.pop();
stack1.push(result + "");
break;
}
stack1.push(result + "");
}
【总结】
1.这样修改代码是正确的
2.但是这段代码仍然错误百出,且错误问题几乎一样
3.说明这段代码我写的逻辑混乱,垃圾代码。
4.程序员思考问题不能一味的线性思考问题。
5.很多的细节没有照顾到,是产生BUG的根本原因,而在修补细节的时候,反而可能造成拆东墙补西墙的效果
6.程序员的修炼之路还很遥远,仍需努力。
原创文章,作者:1402239773,如若转载,请注明出处:https://blog.ytso.com/tech/java/277806.html