题目描述

这个题目其实非常的简单了, 如果大家做过牛客网的华为机试HJ50, 那么你会发现这两个题目基本是一模一样的, 没有什么区别

这里我放上题目链接, 和我写的题解的博客链接

题目链接

题解链接

然后我们言归正传, 我们这个题意是什么的呢?

就是我们有括号和我们的0-9的数字和加减乘除, 然后让我们去计算这个表达式的值是多少

题解

解法一: 投机取巧

实现思路:

这里一定要强调一下, 有时候这个说是投机取巧, 但是这个也正是因为你了解这些语言, 你知道可以不用重复造轮子而带来的便利, 这个其实是值得提倡的, 既然有简单的方法我们一定要知道, 本质原理我们也了解, 这样才是很好的

这里我们可以直接使用Python的eval的库函数直接解决, 比我们上一个难度还要小, 不需要把我们的括号进行替换了

代码实现

s = input()

print(int(eval(s)))

时空复杂度分析

时间复杂度: $O(n)O(n)$

理由如下: 我们还是需要遍历字符串把我们的括号进行一个替换

空间复杂度: $O(1)O(1)$

理由如下: 我们未使用额外的空间

解法二: 递归求解

实现思路

我们还是老套路, 遇到括号就递归下去, 然后用vector来实现我们的栈的操作, 然后我们再去每次计算最内层表达式的值, 这样我们就可以得到我们最后表达式的值, 初始变成正号, 然后初始值是0, 是为了防止我们出现一开始就是负号的情况

图解代码

代码实现

#include <bits/stdc++.h>

using namespace std;

int dfs(string &s, int l, int r) {
    vector<int> st;
    // 这个代表的就是我们的栈
    int len = s.size(), res = 0;
    char op = '+';
    // c初始值是0, 假设初始的符号就是+
    for (int i = l; i <= r; i++) {
        if (isdigit(s[i])) res = res * 10 + (s[i] - '0');
        // 避免多位, 转换成为一个整数
        if (s[i] == '(') {
            int lv = 0;
            int j = i;
            for (; j <= r; j++) {
                if (s[j] == '(')
                    lv += 1;
                else if (s[j] == ')')
                    if (--lv == 0) break;
            }
            res = dfs(s, i + 1, j - 1);
            i = j + 1;
            // 如果是左括号, 我们继续向下递归, 如果我们不是左括号,
            // 如果是右括号我们返回一层
        }
        if (!isdigit(s[i]) || i == r) {
            if (op == '+') {
                st.emplace_back(res);
            } else if (op == '-') {
                st.emplace_back(-res);
            } else if (op == '*') {
                st.back() *= res;
            } else if (op == '/') {
                st.back() /= res;
            }
            op = s[i];
            res = 0;
        }
        // 如果是符号位, 我们考虑出栈计算
    }
    return accumulate(st.begin(), st.end(), 0);
    // 返回整个的值
}

signed main() {
    string s;
    cin >> s;
    cout << dfs(s, 0, s.size() - 1) << "\n";
    return 0;
}

时空复杂度分析

时间复杂度: $O(n)O(n)$

理由如下: 我们会遍历一次我们的字符串

空间复杂度: $O(n)O(n)$

理由如下: 我们要考虑我们不断递归的递归栈的深度和我们每次的vector存了多少的东西