大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。
一、题目
1、算法题目
“给定一个字符串表达式，实现一个基本计算器来计算并返回它的值。”
2、题目描述
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
示例 1： 输入： s = "1 + 1" 输出： 2
示例 2： 输入： s = " 2-1 + 2 " 输出： 3
二、解题
1、思路分析
题意要求给定字符串表达式，实现基本计算器来计算并返回它的值。
这段字符串表达式，可能包含的元素有数字和括号、运算符加号和减号。
只有加减法，可以把括号全都展开来写，例如 2 - （1 - 3）展开成 2 - 1 + 3。
也就是，如果当前位置处于括号之内，则：
- 遇到以 - 号开头的括号，此后的符号都要被翻转
- 遇到以 + 号开头的括号，不变
可以考虑维护一个栈ops，栈顶元素存入根据括号所判断的符号sign：
- 如果遇到+号，则更新sign ← ops.top()
- 如果遇到-号，则更新sign ← -ops.top()
每当遇到左括号，则将当前的sign取值压入栈中。
每当遇到右括号，则从栈中弹出一个元素。
2、代码实现
代码参考：
class Solution { public int calculate(String s) { Deque<Integer> ops = new LinkedList<Integer>(); ops.push(1); int sign = 1; int ret = 0; int n = s.length(); int i = 0; while (i < n) { if (s.charAt(i) == ' ') { i++; } else if (s.charAt(i) == '+') { sign = ops.peek(); i++; } else if (s.charAt(i) == '-') { sign = -ops.peek(); i++; } else if (s.charAt(i) == '(') { ops.push(sign); i++; } else if (s.charAt(i) == ')') { ops.pop(); i++; } else { long num = 0; while (i < n && Character.isDigit(s.charAt(i))) { num = num * 10 + s.charAt(i) - '0'; i++; } ret += sign * num; } } return ret; } }
3、时间复杂度
时间复杂度：O(n)
其中n为字符串s的长度，需要遍历字符串s一次，计算表达式的值。
空间复杂度：O(n)
其中n为字符串s的长度，空间复杂度屈取决于栈的空间，栈中的元素数量不超过n。
三、总结
本题基于栈这一数据结构可以演变出很多种解法。
比如使用双栈，一个栈存放所有的数字，一个栈存放所有数字意外的操作。
然后还是根据符号跟括号判断压入栈的元素。
