题目描述
blablabla
样例
blablabla
算法1
(暴力DFS) $O(n)$
blablabla
时间复杂度
参考文献
难点
对递归时,“递”的部分和“归”的部分的操作
本题的难点在于对递归范围的划分,每次递归进入时处理的范围,以及“归”时怎么返回已经得到的结果的方式(使用同一个哈希表)。
C++ 代码
/*函数式语言 -> 递归求解*/
typedef unordered_map<string, int> MPSI;
class Solution {
public:
int evaluate(string expression) {
int k = 0;
return dfs(expression, k, MPSI());
}
int get_value(string& str, int& k, MPSI vars) {
// 求解 变量 数字 表达式
int value;
if (str[k] == '-' || isdigit(str[k])) {
int i = k + 1;
while (isdigit(str[i])) i ++;
value = stoi(str.substr(k, i - k));
k = i;
} else if (str[k] == '(') {
value = dfs(str, k, vars);
} else {
string name = "";
while (str[k] != ' ' && str[k] != ')') name += str[k ++];
value = vars[name];
}
return value;
}
int dfs(string& str, int& k, MPSI vars) {
int value;
k ++; // 跳过 '('
string type = str.substr(k, 3);
if (type == "let") {
k += 4; // 跳过 'let '
while (str[k] != ')') {
// 如果是 表达式 或者 数字,说明是单独出现的,一定是 let 的返回值
if (str[k] == '(' || str[k] == '-' || isdigit(str[k])) {
value = get_value(str, k, vars);
break; //
}
// 是 变量
string name = "";
while (str[k] != ' ' && str[k] != ')') name += str[k ++];
if (str[k] == ')') {
value = vars[name];
break;
}
// 变量后接 数字或者表达式
k ++; // 跳过空格
vars[name] = get_value(str, k, vars);
k ++; // 跳过空格
}
} else if (type == "add") {
k += 4; // 跳过 "add "
int a = get_value(str, k, vars);
k ++; // 跳过 ' '
int b = get_value(str, k, vars);
value = a + b;
} else if (type == "mul") {
k += 5; // 跳过 "mult "
int a = get_value(str, k, vars);
k ++; // 跳过 ' '
int b = get_value(str, k, vars);
value = a * b;
}
k ++; // 跳过 ')'
return value;
}
};
算法2
(暴力枚举) $O(n)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla