fucking-algorithm
fucking-algorithm copied to clipboard
Published
20 hours ago •
labuladong
labuladong
如何实现一个计算器 :: labuladong的算法小抄
这思路很强，当初学数据结构时，书上是给了一个运算符优先级表格，然后两个栈：数字栈和符号栈，各种压栈出栈，挺复杂的，我自己也是这样写的，看了你的方法，才觉得好简单。
Java版（双向队列模拟栈）
class Solution {
public int calculate(String s) {
Deque<Character> deque = new LinkedList<>();
for(int i = 0; i < s.length(); i++){
//入队的时候就把空格排除在外，省的接下来再额外判断
if(s.charAt(i) != ' '){
deque.addLast(s.charAt(i));
}
}
return helper(deque);
}
private int helper(Deque<Character> deque){
Deque<Integer> stack = new LinkedList<>();
char sign = '+';
int num = 0;
while(deque.size() > 0){
char c = deque.removeFirst();
if(isdigit(c)){
num = num * 10 + (c - '0');
}
if(c == '('){
num = helper(deque);
}
if(!isdigit(c) || deque.size() == 0){
if(sign == '+'){
stack.addLast(num);
}else if(sign == '-'){
stack.addLast(-num);
}else if(sign == '*'){
int pre = stack.removeLast();
stack.addLast(pre*num);
}else if(sign == '/'){
int pre = stack.removeLast();
stack.addLast(pre/num);
}
num = 0;
sign = c;
}
if(c == ')'){
break;
}
}
int res = 0;
while(stack.size() > 0){
int top = stack.removeLast();
res += top;
}
return res;
}
private boolean isdigit(char c){
if(c >= '0' && c <= '9'){
return true;
}
return false;
}
}
感觉递归那里有点问题（可能是我没看懂）
不过递归后处理的位置，即i应该发生改变
由于基本计算器III没法提交（需要会员），我也不知道我写对没有，一下是我改出的CPP版：
#include "iostream"
#include "vector"
using namespace std;
class Solution {
public:
int calculate(string str) {
int subLen;
return solution(str, 0, subLen);
}
int solution(string &str, int start, int &subLen) {
subLen = 1; // 包括（）算式的长度; 1 --> '('
vector<int> stk;
char sign = '+'; // 记录 num 前的符号，初始化为 +
int num = 0;
int n = str.length();
for (int i = start; i < n; i++) {
subLen++;
if (isdigit(str[i])) {
num = num * 10 + (str[i] - '0');
}
if (str[i] == '(') {
subLen = 1; // 清理原来的subLen
num = solution(str, i + 1, subLen);
i += subLen;
// 上面的`subLen = 1`比较重要，否则s[i] = ')' ，结合下面的判断语句，将直接跳出第一层递归，不会继续向后计算
}
// 如果不是数字，就是遇到了下一个符号，
// 之前的数字和符号就要存进栈中
if ((!isdigit(str[i]) && str[i] != ' ') || i == n - 1) {
switch (sign) { //处理s[i] 前面的数
case '+':
stk.push_back(num);
break;
case '-':
stk.push_back(-num);
break;
case '*':
stk.back() *= num; // vector::back() 访问矢量的最后一个元素，它返回对矢量的最后一个元素的引用
break;
case '/':
stk.back() /= num;
break;
}
sign = str[i]; // 更新数字
num = 0; // 数字清零
}
if (str[i] == ')') {
break;
}
}
// 将栈中所有结果求和就是答案
int res = 0;
while (!stk.empty()) {
res += stk.back();
stk.pop_back();
}
return res;
}
};
int main() {
Solution s;
string str;
getline(cin, str);
cout << s.calculate(str);
}
发现我昨天想错了，昨天的代码无法解决多个括号嵌套的问题； 问题的核心其实就是递归解决子问题后，下标的移动问题； 之前在想括号内子问题怎么解决（主要是长度问题，因为子问题解决了，下标位置应该发生改变），于是想要通过函数求解子问题长度，但发现实际难以实现（涉及到括号的匹配问题）； 思考很久后，发现是想复杂了。 其实只要递归的时候 index下标传引用，应该就不用考虑括号里面的子问题了 下面是可能的解法（算是一种在线算法）
#include "iostream"
#include "vector"
using namespace std;
class Solution {
public:
int calculate(string str) {
int index;
return solution(str, index);
}
int solution(string &str, int &index) {
vector<int> stk;
char sign = '+'; // 记录 num 前的符号，初始化为 +
int num = 0;
int n = str.length();
for (; index < n; index++) {
if (isdigit(str[index])) {
num = num * 10 + (str[index] - '0');
}
if (str[index] == '(') {
index++;
num = solution(str, index);
}
// 如果不是数字，就是遇到了下一个符号，
// 之前的数字和符号就要存进栈中
if ((!isdigit(str[index]) && str[index] != ' ') || index == n - 1) {
switch (sign) { //处理s[i] 前面的数
case '+':
stk.push_back(num);
break;
case '-':
stk.push_back(-num);
break;
case '*':
stk.back() *= num; // vector::back() 访问矢量的最后一个元素，它返回对矢量的最后一个元素的引用
break;
case '/':
stk.back() /= num;
break;
}
sign = str[index]; // 更新数字
num = 0; // 数字清零
}
if (str[index] == ')') {
index++;
break;
}
}
// 将栈中所有结果求和就是答案
int res = 0;
while (!stk.empty()) {
res += stk.back();
stk.pop_back();
}
return res;
}
};
int main() {
Solution s;
string str;
getline(cin, str);
cout << s.calculate(str);
}
你这方法简单易懂👍 附一个python完整代码：
class Solution():
def calculate(self,s: str) -> int:
def f(s):
num,sgn,st=0,'+',deque()
while len(s)>0:
c = s.pop(0)
if c.isdigit():
num = 10*num + int(c)
if c=='(': num = f(s)
if len(s)==0 or (not c.isdigit() and not c==' '):
if sgn=='+': st.append(num)
elif sgn=='-': st.append(-num)
elif sgn=='*': st[-1] *= num
elif sgn=='/': st[-1] = int(st[-1]/num)
sgn,num = c,0
if c==')': break
return sum(st)
return f(list(s))
进一步思考了一下，原文中需要计算数值的判断条件
if (not c.isdigit() and c != ' ') or len(s) == 0:
如果改为
if c in ['+','-','*','/',')'] or len(s)==0:
思路会更清晰一些，只有在遇到 + - * / ) 以及len(s)==0 这六种情况下才需要计算数值，并且赋值sgn为c。而且原文中的条件会包括 ( 这一情形，遇到左括号在进入递归 num = helper(s) 结束后，理论上不应该进入该条件，虽然对最后结果没有什么影响。以下为可提交通过的代码：
class Solution():
def calculate(self,s: str) -> int:
def f(s):
num,sgn,st=0,'+',deque()
while len(s)>0:
c = s.pop(0)
if c.isdigit():
num = 10*num + int(c)
if c=='(': num = f(s)
if c in ['+','-','*','/',')'] or len(s)==0:
if sgn=='+': st.append(num)
elif sgn=='-': st.append(-num)
elif sgn=='*': st[-1] *= num
elif sgn=='/': st[-1] = int(st[-1]/num)
sgn,num = c,0
if c==')': break
return sum(st)
return f(list(s))
我分享一下c++的代码
class Solution {
public:
int calculate(string str) {
int index = 0;
return solution(str, index);
}
int solution(string &s, int &index) {
stack<int> tokens;
int num = 0;
char sign = '+';
for (; index < s.size() + 1; ++index) {
char c = s[index];
if (isdigit(c)) {
num = num * 10 + (c - '0');
continue;
}
if (c == '(') {
index++;
num = solution(s, index);
continue;
}
if (!isdigit(c) && c != ' ') {
int temp;
switch (sign) {
case '+':
tokens.push(num);
break;
case '-':
tokens.push(-num);
break;
case '*':
temp = tokens.top();
tokens.pop();
tokens.push(temp * num);
break;
default:
temp = tokens.top();
tokens.pop();
tokens.push(temp / num);
}
num = 0;
sign = c;
}
if (c == ')')
break;
}
int result = 0;
while (!tokens.empty()) {
result += tokens.top();
tokens.pop();
}
return result;
}
};
这道题if(c == ')')稍微换到前面的位置就容易导致结果出错，因为对于(1+1)这样的，会进入不了index==s.size()-1那个判断，这样的代码很不鲁棒性，为了简单一些，直接把边界判断移出去，同时对代码进行了一些修改，去掉重复判断的地方（强迫症），这样就可以随心所欲的用if else if来进行背诵，根本不用管顺序。
class Solution {
public:
int calculate(string s) {
int index = 0;
return helper(s, index);
}
int helper(string s, int& index){
stack<int> nums;
char sign = '+';
int num = 0;
while (index < s.size()){
char c = s[index++];
if (c == ' ') continue;
else if (isdigit(c)) num = 10 * num + (c - '0');
else if (c == '(') num = helper(s, index);
else if (c == ')') break;
else get_into_stack(nums, sign, num, c);
}
get_into_stack(nums, sign, num);
return sum_stack(nums);
}
void get_into_stack(stack<int>& nums, char& sign, int&num, char c='+'){
switch(sign){
case '+': nums.push(num); break;
case '-': nums.push(-num); break;
}
sign = c;
num = 0;
}
int sum_stack(stack<int> nums){
int sum = 0;
while(!nums.empty()){
sum += nums.top();
nums.pop();
}
return sum;
}
};
js版 没有使用list模拟queue 因为会超时
/**
* @param {string} s
* @return {number}
*/
var calculate = function (S) {
i = 0;
// 处理括号需要递归
function helper() {
const stack = [];
let num = 0, sign = '+';// 记录运算符
while (i < S.length) {
const char = S[i];
i++;
// 遇到括号 进入递归处理子序列的计算
if (char == "(") {
num = helper();
}
if (Number.isInteger(+char) && char != ' ') {
num = num * 10 + parseInt(char) // 记录数字
}
if ((isNaN(char) && char != ' ') || i == S.length) {
if (sign === '+') {
stack.push(num);
}
if (sign === '-') {
stack.push(- (num))
}
if (sign === '*') {
const top = stack.pop();
stack.push(top * (num))
}
if (sign === '/') {
const top = stack.pop();
// 如果是负数 -3/2 = -1 向上取整 如果是正数 向下取整
stack.push(parseInt(top / (num)))
}
num = 0;
sign = char;
}
// 遇到出的括号 跳出循环 计算子串的和
if (char == ")") break;
}
return stack.reduce((a, b) => a + b);
}
return helper();
};
772 java, 1ms, faster than 90+%
class OnePass_20220709 {
private int i;
private int n;
public int calculate(String s) {
this.n = s.length();
this.i = 0;
return helper(s);
}
private int helper(String s) {
int result = 0;
int lastNum = 0;
char operation = '+';
int curNum = 0;
for (; i < n; ++i) {
char ch = s.charAt(i);
if (Character.isDigit(ch)) {
curNum = curNum * 10 + ch -'0';
} else if ('(' == ch) {
++i;
curNum = helper(s);
++i;
if (i < n) ch = s.charAt(i);
}
if (i == n-1 || ')' == ch || (
!Character.isDigit(ch) && ch != ' ')){
if ('+' == operation || '-' == operation) {
result += lastNum;
lastNum = ('+' == operation) ? curNum : -curNum;
} else if ('*' == operation) {
lastNum = lastNum * curNum;
} else if ('/' == operation) {
lastNum = lastNum / curNum;
}
curNum = 0;
operation = ch;
}
if (')' == ch) break;
}
result += lastNum;
return result;
}
}
附上一个只有加减的C++版本。使用了全局变量index和while(index < s.size())来控制每次递归的输入，即一定是括号后的下一个元素。需要注意的是，由于代码中进入while循环后index直接自增，所以入栈条件就变成了index >= s.size()。
我还看到有题解是将字符串s转换成了双端队列或者list来做，每次进入循环都将第一个元素pop，但是我个人感觉有点儿麻烦。
class Solution {
public:
int calculate(string s) {
// 计算器
// 带括号和 + -
this->s = s;
return calcu();
}
string s;
int index = 0;
int calcu(){
// 碰到括号就递归，＋-用栈
stack<int> st;
char sign = '+'; // 将第一个数的初始符号位设定为'+'
int num = 0; // 记录算式中的数字
while(index < s.size()){
char c = s[index++];
if(isdigit(c)){
// 当前为数字，连续读取，将char转为int
num = num * 10 + (c - '0'); // 防止整形溢出
}
// 遇到左括号开始递归计算 num
if(c == '('){
num = calcu(); // 利用全局变量index来记录当前遍历的索引
}
if((!isdigit(c) && c != ' ' ) || index >= s.size()){
// 如果不是数字也不是空格 就是遇到了下一个数学运算符
// 将之前的数字与其对应的sign push到栈中
switch(sign){
case '+':
st.push(num);
break;
case '-':
st.push(-num);
break;
}
// 更新符号为当前遍历到的运算符
sign = c;
// 将数字清零
num = 0;
}
if(c == ')'){
// 遇到右括号，递归结束
break;
}
}
// 将栈中所有结果求和就是答案
int res = 0;
while(!st.empty()){
res += st.top();
st.pop();
}
return res;
}
};
