AcWing 151. 表达式计算4
原题链接
中等
作者:
wjie
,
2020-07-29 20:51:36
,
所有人可见
,
阅读 499
#include <iostream>
#include <cstdio>
#include <stack>
using namespace std;
stack<char> operates;
stack<int> numbers;
string formula;
bool isDigit(char c)
{
return c >= '0' && c <= '9';
}
void getNumbers(int& i, bool minus)
{
int res = 0;
while (isDigit(formula[i]))
{
res = res * 10 + formula[i] - '0';
i++;
}
i--;
if (minus) res = -res;
numbers.push(res);
}
int exp(int a, int b)
{
int res = 1;
while (b)
{
if (b & 1) res *= a;
a *= a;
b >>= 1;
}
return res;
}
void calc()
{
int b = numbers.top();
numbers.pop();
int a = numbers.top();
numbers.pop();
char c = operates.top();
operates.pop();
int res;
if (c == '+') res = a + b;
else if (c == '-') res = a - b;
else if (c == '/') res = a / b;
else if (c == '*') res = a * b;
else res = exp(a, b);
numbers.push(res);
}
int main()
{
cin >> formula;
int n = formula.size();
for (int i = 0; i < n; ++i) formula = "(" + formula;
formula += ")";
for (int i = 0; i < formula.size(); ++i)
{
char c = formula[i];
// cout << c << endl;
if (isDigit(c)) getNumbers(i, false);
else if (c == '+')
{
while (operates.size() && operates.top() != '(') calc();
operates.push(c);
}
else if (c == '-')
{
if (isDigit(formula[i+1]) && formula[i-1] == '(')
{
getNumbers(++i, true);
}
else
{
while (operates.size() && operates.top() != '(') calc();
operates.push(c);
}
}
else if (c == '*' || c == '/')
{
// cout << operates.size() << endl;
while (operates.size() && (operates.top() == '*' || operates.top() == '/' || operates.top() == '^')) calc();
// cout << operates.size() << endl;
operates.push(c);
}
else if (c == '^')
{
while (operates.size() && operates.top() == '^') calc();
operates.push(c);
}
else if (c == ')')
{
while (operates.size() && operates.top() != '(') calc();
operates.pop();
}
else operates.push(c);
}
printf("%d", numbers.top());
return 0;
}