一、题目描述
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
示例 1：
输入：s = "1 + 1" 输出：2
示例 2：
输入：s = " 2-1 + 2 " 输出：3
示例 3：
输入：s = "(1+(4+5+2)-3)+(6+8)" 输出：23
提示：
1 <= s.length <= 3 * 105s由数字、'+'、'-'、'('、')'、和' '组成s表示一个有效的表达式- '+' 不能用作一元运算(例如， "+1" 和
"+(2 + 3)"无效) - '-' 可以用作一元运算(即 "-1" 和
"-(2 + 3)"是有效的) - 输入中不存在两个连续的操作符
- 每个数字和运行的计算将适合于一个有符号的 32位 整数
二、思路分析
三、代码参考
1、Java
class Solution {
public int calculate(String s) {
// 创建栈空间
Stack<Integer> stack = new Stack<>();
// 用来表示正负号，1 为 + ， -1 位 - ，默认为正数
int sign = 1;
// 用来记录运算结果
int result = 0;
// 循环遍历字符串
for(int i = 0; i < s.length(); i++){
// 获取当前字符
char str = s.charAt(i);
// 判断是否为数字类型
if(Character.isDigit(str)){
// 通过 - '0' 这个操作把字符转换为整数
int value = str - '0';
// 查看后面是否字符仍为数字，即数字是否为多位数，如果是需要拼接好数字
while(i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))){
// i 向后移动
i++;
// 数字拼接，如
// 12 = 1 * 10 + 2
// 123 = 12 * 10 + 3
value = value * 10 + s.charAt(i) - '0';
}
// 把获取到的结果赋值给 result
result = result + sign * value;
}
// 如果是 + 符号，则 sign 为 1
else if(str == '+'){
sign = 1;
}
// 如果是 - 符号，则 sign 为 -1
else if(str == '-'){
sign = -1;
}
// 判断是否是 '('
else if(str == '('){
// 先把在遇到 '(' 之前的结果放入到栈中
stack.push(result);
// 然后 result 结果置空，为了等下计算括号里面的结果
result = 0;
// 再把左括号前面的符号放入到栈中
stack.push(sign);
// 回归默认值
sign = 1;
}
// 判断是否为 ')'
else if(str == ')'){
// 取出栈顶的元素，此时的栈顶元素是 '(' 前的符号
int symbol = stack.pop();
// 再获取栈顶元素，此时的栈顶元素是 '(' 前的运算结果
int stackResult = stack.pop();
// 计算结果并将结果赋值给 result
result = stackResult + symbol * result;
}
}
// 返回结果
return result;
}
}2、Python
class Solution(object):
def calculate(self, s):
# 创建栈空间
stack = list()
# 用来表示正负号，1 为 + ， -1 位 - ，默认为正数
sign = 1
# 用来记录运算结果
result = 0
# 初始化 i
i = 0
# 循环遍历字符串
while i < len(s):
# 获取当前字符
str = s[i]
# ' ' 空字符不需要做处理，下一个就好
if str == ' ' :
i += 1
# 判断是否为数字类型
elif str.isdigit() :
# 把字符类型转换成数字类型
value = ord(s[i]) - ord('0')
# 查看后面是否字符仍为数字，即数字是否为多位数，如果是需要拼接好数字
while i + 1 < len(s) and s[i + 1].isdigit():
# i 向后移动
i += 1
# 数字拼接，如
# 12 = 1 * 10 + 2
# 123 = 12 * 10 + 3
value = value * 10 + ord(s[i]) - ord('0')
# 把获取到的结果赋值给 result
result += value * sign
i += 1
# 如果是 + 符号，则 sign 为 1
elif str == '+' :
sign = 1
i += 1
# 如果是 - 符号，则 sign 为 -1
elif str == '-' :
sign = -1
i += 1
# 判断是否是 '('
elif str == '(' :
# 先把在遇到 '(' 之前的结果放入到栈中
stack.append(result)
# 然后 result 结果置空，为了等下计算括号里面的结果
result = 0
# 再把左括号前面的符号放入到栈中
stack.append(sign)
# 回归默认值
sign = 1
i += 1
# 判断是否为 ')'
elif str == ')' :
# 取出栈顶的元素，此时的栈顶元素是 '(' 前的符号
symbol = stack.pop()
# 再获取栈顶元素，此时的栈顶元素是 '(' 前的运算结果
stackResult = stack.pop()
# 计算结果并将结果赋值给 result
result = stackResult + symbol * result
i += 1
# 返回结果
return result
