Basic Calculator
系列在 LeetCode
上有三道:
这类题目重点在于解决运算的优先级问题,需要将数字和运算符按优先级依次处理以得到正确结果。
LeetCode 224 给你一个字符串表达式 s ,请你实现一个基本计算器来计算并返回它的值。
注意:不允许使用任何将字符串作为数学表达式计算的内置函数,比如 eval() 。
示例 1:
输入:s = “1 + 1” 输出:2
示例 2:
输入:s = “ 2-1 + 2 “ 输出:3
示例 3:
输入:s = “(1+(4+5+2)-3)+(6+8)” 输出:23
题解 保存每个数字前的符号并相加。
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 class Solution { public int calculate (String s) { int n = s.length(); int [] signs = new int [n]; signs[0 ] = 1 ; int sign = 1 , result = 0 , sIdx = 0 ; for (int i = 0 ; i < n; i++) { char cur = s.charAt(i); if (cur == '+' ) sign = signs[sIdx]; else if (cur == '-' ) sign = -signs[sIdx]; else if (cur == '(' ) signs[++sIdx] = sign; else if (cur == ')' ) sIdx--; else if (isDigit(cur)) { long num = cur - '0' ; while (i + 1 < n && isDigit(s.charAt(i + 1 ))) num = num * 10 + s.charAt(++i) - '0' ; result += sign * num; } } return result; } private boolean isDigit (char num) { return '0' <= num && num <= '9' ; } }
LeetCode 227 给你一个字符串表达式 s ,请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。
注意:不允许使用任何将字符串作为数学表达式计算的内置函数,比如 eval() 。
示例 1:
输入:s = “3+2*2” 输出:7
示例 2:
输入:s = “ 3/2 “ 输出:1
示例 3:
输入:s = “ 3+5 / 2 “ 输出:5
题解 先遍历计算乘除,再计算加减。
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 public class Solution { public int calculate (String s) { char sign = '+' ; int len = s.length(), idx = 0 ; int [] nums = new int [(len + 1 ) / 2 ]; for (int i = 0 ; i < len; i++) { char cur = s.charAt(i); if (cur == ' ' ) continue ; int num = 0 ; if (isDigit(cur)) { num = cur - '0' ; while (i + 1 < len && isDigit(s.charAt(i + 1 ))) num = num * 10 - '0' + s.charAt(++i); } switch (sign) { case '+' : nums[idx++] = num; break ; case '-' : nums[idx++] = -num; break ; case '*' : nums[idx - 1 ] *= num; break ; case '/' : nums[idx - 1 ] /= num; break ; } sign = cur; } int result = 0 ; for (int i = 0 ; i < idx; i++) result += nums[i]; return result; } private boolean isDigit (char ch) { return '0' <= ch && ch <= '9' ; } }
LeetCode 772 实现一个基本的计算器来计算简单的表达式字符串。
表达式字符串只包含非负整数,算符 +、-、*、/ ,左括号 ( 和右括号 ) 。整数除法需要 向下截断 。
你可以假定给定的表达式总是有效的。所有的中间结果的范围为 [-231, 231 - 1] 。
示例 1:
输入:s = “1 + 1” 输出:2
示例 2:
输入:s = “6 - 4 / 2” 输出:4
示例 3:
输入:s = “2 * ( 5 + 5 * 2 ) / 3 + ( 6 / 2 + 8 )” 输出:21
示例 4:
输入:s = “( 2 + 6 * 3 + 5 - 3 * 14 / 7 + 2 ) * 5 ) + 3” 输出:-12
示例 5:
输入:s = “0” 输出:0
题解 去除括号带来的影响,相比于 227,差别仅在于将括号内的字符串递归地计算作为整体进行处理。
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 public class Solution { public int calculate (String s) { char sign = '+' ; int len = s.length(), idx = 0 ; int [] nums = new int [(len + 1 ) / 2 ]; for (int i = 0 ; i < len; i++) { char cur = s.charAt(i); if (cur == ' ' ) continue ; int num = 0 ; if (isDigit(cur)) { num = cur - '0' ; while (i + 1 < len && isDigit(s.charAt(i + 1 ))) num = num * 10 - '0' + s.charAt(++i); } else if (cur == '(' ) { int j = findClosing(s.substring(i)); num = calculate(s.substring(i + 1 , i + j)); i += j; } switch (sign) { case '+' : nums[idx++] = num; break ; case '-' : nums[idx++] = -num; break ; case '*' : nums[idx - 1 ] *= num; break ; case '/' : nums[idx - 1 ] /= num; break ; } sign = cur; } int result = 0 ; for (int i = 0 ; i < idx; i++) result += nums[i]; return result; } private boolean isDigit (char ch) { return '0' <= ch && ch <= '9' ; } private int findClosing (String s) { int len = 0 , depth = 0 ; for (char c : s.toCharArray()) { if (c == '(' ) depth++; else if (c == ')' ) { depth--; if (depth == 0 ) break ; } len++; } return len; } }