1、问题
描述
请写一个整数计算器,支持加减乘三种运算和括号。
数据范围:0≤∣s∣≤100,保证计算结果始终在整型范围内
2、代码
public ArrayList<Integer> function(String s, int index) { Stack<Integer> stack = new Stack<Integer>(); int num = 0; char op = '+'; int i; //从指定位置循环遍历给定字符串 for (i = index; i < s.length(); i++) { //判断是否为数字 if (s.charAt(i) >= '0' && s.charAt(i) <= '9') { //将字符转换为数字 num = num * 10 + s.charAt(i) - '0'; //判断是否到了最后一个字符,如果不是就继续跳出循环 if (i != s.length() - 1) continue; } //判断字符是不是'(' if (s.charAt(i) == '(') { //如果是就递归调用函数function(),作用是将后面的字符看作一个整体,直到碰到字符')' ArrayList<Integer> res = function(s, i + 1); //将递归函数的返回值第一个数赋值给num num = res.get(0); //将递归函数的第二个值赋值给i i = res.get(1); //判断是否是最后一个字符,如果是跳出循环 if (i != s.length() - 1) continue; } //将字符匹配 switch (op) { //将num入栈 case '+': stack.push(num); break; //将num的相反数入栈 case '-': stack.push(-num); break; //将栈顶和当前num相乘后入栈 case '*': int temp = stack.pop(); stack.push(temp * num); break; } //将num归零 num = 0; //判断是否为字符')' if (s.charAt(i) == ')') //如果是就直接退出循环 break; else //如果不是就一定是加减乘符号,将op重新设置 op = s.charAt(i); } int sum = 0; //栈中元素相加 while (!stack.isEmpty()) sum += stack.pop(); //设置一个新的链表 ArrayList<Integer> temp = new ArrayList<Integer>(); //第一个元素存储递归一次函数的数的和 temp.add(sum); //将递归到的位置赋值给第二个数 temp.add(i); //返回temp return temp; } public int solve(String s) { //调用递归函数 ArrayList<Integer> res = function(s, 0); //返回第一个值 return res.get(0); }
3、总结:本次表达式的实现利用了递归算法,递归是指一段程序直接或者间接调用自身的一种方法,通过这种形式执行需要进行一些固定步骤的许多操作,它可以把一个复杂并且庞大的问题简单化,通过专注于解决它分化出来的小问题从而解决大问题,从而大大减少我们的代码量,是提高我们编码效率的很好方法。