如何实现一个计算器 :: labuladong的算法小抄 #1047
Replies: 30 comments 10 replies
-
|
这思路很强，当初学数据结构时，书上是给了一个运算符优先级表格，然后两个栈：数字栈和符号栈，各种压栈出栈，挺复杂的，我自己也是这样写的，看了你的方法，才觉得好简单。 |
Beta Was this translation helpful? Give feedback.
-
|
可是你这个方法会超时啊 |
Beta Was this translation helpful? Give feedback.
-
|
对不起，我错了，用collections.deque是不会超时的，如果用单纯的list是会超时的 |
Beta Was this translation helpful? Give feedback.
-
|
有java版本吗，处理括号老是怪怪的 |
Beta Was this translation helpful? Give feedback.
-
|
list超时是因为 |
Beta Was this translation helpful? Give feedback.
-
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;
}
} |
Beta Was this translation helpful? Give feedback.
-
|
好像计算器处理不了3*-5这样的情况 |
Beta Was this translation helpful? Give feedback.
-
|
因为题目要求中说到过“输入中不存在两个连续的操作符” |
Beta Was this translation helpful? Give feedback.
-
|
感觉递归那里有点问题（可能是我没看懂） #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);
} |
Beta Was this translation helpful? Give feedback.
-
|
发现我昨天想错了，昨天的代码无法解决多个括号嵌套的问题； #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);
} |
Beta Was this translation helpful? Give feedback.
-
|
改用vector能用back操作好方便，赞！不过 |
Beta Was this translation helpful? Give feedback.
-
|
如果char字符等于），index不需要++了，因为进入下一次循环，index会++的。 |
Beta Was this translation helpful? Give feedback.
-
|
你这方法简单易懂👍 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)) |
Beta Was this translation helpful? Give feedback.
-
|
进一步思考了一下，原文中需要计算数值的判断条件 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)) |
Beta Was this translation helpful? Give feedback.
-
|
这么换了以后224过不了 |
Beta Was this translation helpful? Give feedback.
-
|
Beta Was this translation helpful? Give feedback.
-
|
我分享一下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;
}
}; |
Beta Was this translation helpful? Give feedback.
-
|
这里index会越界啊？ |
Beta Was this translation helpful? Give feedback.
-
|
我找到了 python中的 List 要用 from typing import List 导入 |
Beta Was this translation helpful? Give feedback.
-
|
这道题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;
}
}; |
Beta Was this translation helpful? Give feedback.
-
|
棒，get_into_stack 里面的后续应该不用更新sign 和 num了 |
Beta Was this translation helpful? Give feedback.
-
|
贴一个你这个思路的java版本 |
Beta Was this translation helpful? Give feedback.
-
|
class Solution { } |
Beta Was this translation helpful? Give feedback.
-
|
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();
}; |
Beta Was this translation helpful? Give feedback.
-
|
LeetCode 772 Test Case Wrong Answer |
Beta Was this translation helpful? Give feedback.
-
|
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;
}
} |
Beta Was this translation helpful? Give feedback.
-
|
没看懂加减法中的（i == s.size() - 1）为何要单独处理？ |
Beta Was this translation helpful? Give feedback.
-
|
附上一个只有加减的C++版本。使用了全局变量 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;
}
}; |
Beta Was this translation helpful? Give feedback.
-
|
最后一句话说的真好哈哈哈 |
Beta Was this translation helpful? Give feedback.
-
|
// 不直接使用栈的解法如下。其中，+和-的处理逻辑相同，*和/的处理逻辑相同。(力扣227题) class Solution {
public:
int calculate(string s) {
int num = 0;
for(int i = 0, n = s.size(), temp; i < n; )
if(isNum(s[i]))
num *= 10, num += s[i++] - '0';
else
switch(s[i]) {
case '+':
temp = i;
while(++i < n)
if(s[i]=='+' || s[i]=='-')
break;
num += calculate(s.substr(++temp, i-temp));
break;
case '-':
temp = i;
while(++i < n)
if(s[i]=='+' || s[i]=='-')
break;
num -= calculate(s.substr(++temp, i-temp));
break;
case '*':
temp = 0;
while(++i < n)
if(isNum(s[i])) temp *= 10, temp += s[i] - '0';
else if(s[i]==' ') continue;
else break;
num *= temp;
break;
case '/':
temp = 0;
while(++i < n)
if(isNum(s[i])) temp *= 10, temp += s[i] - '0';
else if(s[i]==' ') continue;
else break;
num /= temp;
break;
case ' ':
++i;
}
return num;
}
bool isNum(char& cha) {return cha >= '0' && cha <= '9';}
}; |
Beta Was this translation helpful? Give feedback.
-
|
复杂一点的话，用编译原理比这个方便 |
Beta Was this translation helpful? Give feedback.
-
|
ChatGPT 翻译的Java版本似乎有错 当字符不为 数字时，仅当当前字符为运算符时才去更新Sign |
Beta Was this translation helpful? Give feedback.
-
|
Golang版本，chatGPT生成的会重复处理被递归部分的数据，导致结果错误 func calculate(s string) int { |
Beta Was this translation helpful? Give feedback.
-
|
Beta Was this translation helpful? Give feedback.
-
Golang版本func calculate(s string) int {
res, _ := cal(s, 0)
return res
}
func cal(s string, start int) (res int, next int) {
var sign byte = '+'
stack := make([]int, 0)
num := 0
for i := start; i < len(s); {
if s[i] >= '0' && s[i] <= '9' {
for ; i < len(s) && s[i] >= '0' && s[i] <= '9'; i++ {
num = num*10 + int(s[i]-'0')
}
} else if s[i] == ' ' {
i++
continue
} else if s[i] == '(' {
num, i = cal(s, i+1)
} else if s[i] == ')' {
next = i + 1
break
} else {
sign = s[i]
i++
continue
}
switch sign {
case '-':
stack = append(stack, -num)
case '+':
stack = append(stack, num)
case '*':
prev := stack[len(stack)-1]
stack[len(stack)-1] = prev * num
case '/':
prev := stack[len(stack)-1]
stack[len(stack)-1] = prev / num
}
num = 0
}
for _, v := range stack {
res += v
}
return
} |
Beta Was this translation helpful? Give feedback.
-
|
一、字符串转整数中n = 10 * n + (ord(c) - ord('0'))转ASCII码是必须的吗？ 为什么不能直接 n = 10*n + int(c) |
Beta Was this translation helpful? Give feedback.
-
|
class Solution { }; |
Beta Was this translation helpful? Give feedback.
-
switch (sign) {
int pre;这里 |
Beta Was this translation helpful? Give feedback.
and others
-
文章链接点这里：如何实现一个计算器
评论礼仪 见这里，违者直接拉黑。
Beta Was this translation helpful? Give feedback.
All reactions