BM49. [表达式求值]
https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295
BM49. 表达式求值
题目的主要信息：
- 支持+ - *三种符号的运算器，其中优先级+ - 是一级，*更高一级
- 支持括号运算
方法一：栈 + 递归
具体做法：
对于上述两个要求，我们要考虑的是两点，一是处理运算优先级的问题，二是处理括号的问题。
- 优先级处理我们可以借助栈，当遇到符号的时候如果是+，正常入栈，如果是-，则将其相反数入栈，如果是*，则将栈中内容弹出与后一个元素相乘再入栈，最后将栈中所有元素相加即可。
- 括号的处理我们可以借助递归，将括号内的运算视为一个子问题，由此来简化。
class Solution {
public:
vector<int> function(string s, int index){
stack<int> stack;
int num = 0;
char op = '+';
int i;
for (i = index; i < s.length(); i++) {
//数字转换成int数字
if(isdigit(s[i])){
num = num * 10 + s[i] - '0';
if(i != s.length() - 1)
continue;
}
//碰到'('时，把整个括号内的当成一个数字处理
if(s[i] == '('){
vector<int> res = function(s, i + 1);
num = res[0];
i = res[1];
if(i != s.length() - 1)
continue;
}
switch (op) {
case '+': //加减号先入栈
stack.push(num);
break;
case '-':
stack.push(-num);
break;
case '*': //优先计算乘号
int temp = stack.top();
stack.pop();
stack.push(temp * num);
break;
}
num = 0;
if(s[i] == ')')
break;
else
op = s[i];
}
int sum = 0;
while(!stack.empty()){ //栈中元素相加
sum += stack.top();
stack.pop();
}
return vector<int> {sum, i};
}
int solve(string s) {
return function(s, 0)[0];
}
};
复杂度分析：
- 时间复杂度：
，n为字符串长度，相当于遍历一遍
- 空间复杂度：
方法二：数组 + 递归
具体做法：
递归将式子分成子块：单独数字或者去掉括号的部分组成一个子块，加入elems中，同时用一个数组记录符号。
去掉括号依赖两个数组统计左右括号，并比较数量来决定。
由此，分成了子块和运算符。
然后遍历运算符的数组，遇到一个乘号需要判断其后一位是否是乘号*,如果是则需要递归乘上后面的子块，然后再计算当前的加减号，最后所有结果加起来即可。
class Solution {
public:
int solve(string s) {
//返回对应数值
if (s.empty())
return 0;
else
{
int temp = 0;
//组合数字
for (size_t i = 0; i < s.size(); i++)
if (s[i] >= '0'&&s[i] <= '9')
{
temp = 10 * temp + (s[i] - '0');
if (i == s.size() - 1)
return temp;
}
else//如果是式子则将式子分块
break;
}
//将式子分块
vector<string> elems;//保存元素块
vector<char> op; //保存该层式子的运算符
vector<char> left;//记录左括号
vector<char> right;//记录右括号
op.push_back('+');//为了将结果加入result第一个运算符必须是+
int i = 0; //当前元素块为i,从0开始
for (auto iter = s.begin(); iter != s.end(); )
{
if (*iter >= '0' && *iter <= '9')//将数值型元素块加入elems
{
elems.push_back("");
for (; iter != s.end() && *iter >= '0' && *iter <= '9'; iter++)
elems[i].push_back(*iter);
i++;
}
else if (*iter == '+' || *iter == '-' || *iter == '*')//将运算符加入op
{
op.push_back(*iter);
iter++;
}
else if (*iter == '(')//将带括号的元素块去掉最外侧括号后加入elems
{
elems.push_back("");
std::string& temp = elems[i];
while (iter != s.end() && (left.size() != right.size() || *iter == '('))
{
if (*iter == '(')
left.push_back(*iter);
else if (*iter == ')')
right.push_back(*iter);
temp.push_back(*iter);
iter++;
}
temp = temp.substr(1, temp.size() - 2);//去掉最外侧括号
i++;
}
else iter++;
}
//计算当前分式子的值
int res = 0;
for (int i = 0; i < op.size(); i++)
{
char o = op[i];
if (i + 1 < op.size())//先预测后一位运算符是不是*
{
int temp = solve(elems[i]);
while(i + 1 < op.size() && op[i + 1] == '*')//如果后面的*，则先计算乘
{
temp *= solve(elems[i + 1]); //递归
i++;
}
switch (o)//当前符号进行加减处理
{
case '+': res += temp;
break;
case '-': res -= temp;
break;
}
}
else//若乘法已经算过了，只剩下加减
{
switch (o)
{
case '+': res += solve(elems[i]);
break;
case '-': res -= solve(elems[i]);
break;
}
}
}
return res;//返回结果
}
};
复杂度分析：
- 时间复杂度：
- 空间复杂度：
腾讯公司福利 448人发布
