class Solution {
public:
int calculate(string s)
{
stack<int> figure;
stack<char> ope;
string temp;
for(int i = 0;i < s.size();i++)
{
if(s[i] == ' ')
{
}
else if(s[i] == '*' ||s[i] == '/')
{
figure.push(atoi(temp.c_str()));
temp = "";
if(!ope.empty())
{
if(ope.top() == '*')
{
int a = figure.top();
figure.pop();
int b = figure.top();
figure.pop();
figure.push(b * a);
ope.pop();
}
else if(ope.top() == '/')
{
int a = figure.top();
figure.pop();
int b = figure.top();
figure.pop();
figure.push(b / a);
ope.pop();
}
}
ope.push(s[i]);
}
else if(s[i] == '+' ||s[i] == '-')
{
if(figure.empty())
figure.push(0);
figure.push(atoi(temp.c_str()));
temp = "";
while(!ope.empty())
{
if(ope.top() == '+')
break;
else if(ope.top() == '*')
{
int a = figure.top();
figure.pop();
int b = figure.top();
figure.pop();
figure.push(b * a);
ope.pop();
}
else if(ope.top() == '/')
{
int a = figure.top();
figure.pop();
int b = figure.top();
figure.pop();
figure.push(b / a);
ope.pop();
}
else if(ope.top() == '-')
{
int a = figure.top();
figure.pop();
int b = figure.top();
figure.pop();
figure.push(b - a);
ope.pop();
}
}
ope.push(s[i]);
}
else
temp += s[i];
if(i == s.size() - 1)
{
if(temp != "")
{
figure.push(atoi(temp.c_str()));
temp = "";
}
}
}
while(!ope.empty())
{
if(ope.top() == '*')
{
int a = figure.top();
figure.pop();
int b = figure.top();
figure.pop();
figure.push(b * a);
ope.pop();
}
else if(ope.top() == '/')
{
int a = figure.top();
figure.pop();
int b = figure.top();
figure.pop();
figure.push(b / a);
ope.pop();
}
else if(ope.top() == '-')
{
int a = figure.top();
figure.pop();
int b = figure.top();
figure.pop();
figure.push(b - a);
ope.pop();
}
else
{
int a = figure.top();
figure.pop();
int b = figure.top();
figure.pop();
figure.push(b + a);
ope.pop();
}
}
return figure.top();
}
};
算法思路:
因为写过了基本计算器|,所以在做这个计算器||的时候感觉还好,
因为乘除法优先级高于加减法,所以检测到乘除运算符时每次都可以检测运算栈栈顶是否为*/,如果检测到的是*/则先进行运算,再压入栈顶
而加减法优先级较低,所以检测到加减运算符的时候,每次都需要检测运算栈栈顶是否为*/-,如果检测到的是*/则先进行运算,再压入栈顶
最后若运算栈不空,则继续运算