1. 题⽬链接:227.基本计算器II
2. 题⽬描述:
题⽬解析:
⼀定要认真看题⽬的提⽰,从提⽰中我们可以看到这道题:
• 只有「加减乘除」四个运算;
• 没有括号;
• 并且每⼀个数都是⼤于等于0 的;
这样可以⼤⼤的「减少」我们需要处理的情况。
3. 解法(栈):
算法思路:
由于表达式⾥⾯没有括号,因此我们只⽤处理「加减乘除」混合运算即可。根据四则运算的顺序,我 们可以先计算乘除法,然后再计算加减法。由此,我们可以得出下⾯的结论:
• 当⼀个数前⾯是'+' 号的时候,这⼀个数是否会被⽴即计算是「不确定」的,因此我们可以先压 ⼊栈中;
• 当⼀个数前⾯是'-' 号的时候,这⼀个数是否被⽴即计算也是「不确定」的,但是这个数已经 和前⾯的-号绑定了,因此我们可以将这个数的相反数压⼊栈中;
• 当⼀个数前⾯是'*' 号的时候,这⼀个数可以⽴即与前⾯的⼀个数相乘,此时我们让将栈顶的元 素乘上这个数;
• 当⼀个数前⾯是'/' 号的时候,这⼀个数也是可以⽴即被计算的,因此我们让栈顶元素除以这个 数。 当遍历完全部的表达式的时候,栈中剩余的「元素之和」就是最终结果。
C++算法代码:
class Solution
{
public:
int calculate(string s)
{
vector<int>answer; //存储栈
char key='+'; //记录数字前的运算符
for(int i=0;i<s.size();)
{
//空格
if(s[i]==' ')
{
i++;
}
//运算符
if(!isdigit(s[i]))
{
key=s[i];
}
//数字字符
else
{
int temp=0; //读取数字
while(isdigit(s[i]))
{
temp*=10;
temp+=s[i]-'0';
i++;
}
if(key=='*')
{
answer.back()*=temp;
}
else if(key=='/')
{
answer.back()/=temp;
}
else if(key=='-')
{
answer.push_back(-temp);
}
else
{
answer.push_back(temp);
}
continue;
}
i++;
}
//求和
int sum=0;
for(int i=0;i<answer.size();i++)
{
sum+=answer[i];
}
return sum;
}
};
Java算法代码:
class Solution
{
public int calculate(String _s)
{
Deque<Integer> st = new ArrayDeque<>();
char op = '+';
int i = 0, n = _s.length();
char[] s = _s.toCharArray();
while (i < n)
{
if (s[i] == ' ') i++;
else if (s[i] >= '0' && s[i] <= '9')
{
int tmp = 0;
while (i < n && s[i] >= '0' && s[i] <= '9')
{
tmp = tmp * 10 + (s[i] - '0');
i++;
}
if (op == '+') st.push(tmp);
else if (op == '-') st.push(-tmp);
else if (op == '*') st.push(st.pop() * tmp);
else st.push(st.pop() / tmp);
}
else
{
op = s[i];
i++;
}
}
// 统计结果
int ret = 0;
while (!st.isEmpty())
{
ret += st.pop();
}
return ret;
}
}
标签:char,int,可以,计算器,个数,II,算法,栈中
From: https://blog.csdn.net/2301_79580018/article/details/141688883