<p>Given a string <code>s</code> representing a valid expression, implement a basic calculator to evaluate it, and return <em>the result of the evaluation</em>.</p>

<p><strong>Note:</strong> You are <strong>not</strong> allowed to use any built-in function which evaluates strings as mathematical expressions, such as <code>eval()</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;1 + 1&quot;
<strong>Output:</strong> 2
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot; 2-1 + 2 &quot;
<strong>Output:</strong> 3
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;(1+(4+5+2)-3)+(6+8)&quot;
<strong>Output:</strong> 23
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 3 * 10<sup>5</sup></code></li>
	<li><code>s</code> consists of digits, <code>&#39;+&#39;</code>, <code>&#39;-&#39;</code>, <code>&#39;(&#39;</code>, <code>&#39;)&#39;</code>, and <code>&#39; &#39;</code>.</li>
	<li><code>s</code> represents a valid expression.</li>
	<li><code>&#39;+&#39;</code> is <strong>not</strong> used as a unary operation (i.e., <code>&quot;+1&quot;</code> and <code>&quot;+(2 + 3)&quot;</code> is invalid).</li>
	<li><code>&#39;-&#39;</code> could be used as a unary operation (i.e., <code>&quot;-1&quot;</code> and <code>&quot;-(2 + 3)&quot;</code> is valid).</li>
	<li>There will be no two consecutive operators in the input.</li>
	<li>Every number and running calculation will fit in a signed 32-bit integer.</li>
</ul>

#include <algorithm>
#include <cassert>
#include <charconv>
#include <cstddef>
#include <iterator>
#include <optional>
#include <string>
#include <string_view>
#include <vector>

using namespace std;
class Solution {
 public:
  int calculate(string s) {
    auto* const root = buildTree(s);
    return reduceTree(root);
  }

 private:
  struct Node {
    char op{' '};
    int number{0};
    Node* left{nullptr};
    Node* right{nullptr};
  };
  struct Op {
    size_t index;
    int nesting_level;
  };
  auto buildTree(std::string_view const s) -> Node* {
    if (s.empty() || std::all_of(s.cbegin(), s.cend(),
                                 [](char const c) { return c == ' '; })) {
      return nullptr;
    }

    auto last_non_nested_plus_index = -1;
    auto last_non_nested_minus_index = -1;
    auto has_any_operators = false;
    auto nesting_level = 0;
    for (size_t i = 0; i < s.size(); ++i) {
      auto const index_from_back = s.size() - i - 1;
      switch (s[index_from_back]) {
        case '(':
          ++nesting_level;
          break;
        case ')':
          --nesting_level;
          break;
        case '-':
          if (last_non_nested_minus_index == -1 && nesting_level == 0) {
            last_non_nested_minus_index = static_cast<int>(index_from_back);
          }
          has_any_operators = true;
          break;
        case '+':
          if (last_non_nested_plus_index == -1 && nesting_level == 0) {
            last_non_nested_plus_index = static_cast<int>(index_from_back);
          }
          has_any_operators = true;
        default:
          break;
      }
      if (last_non_nested_plus_index != -1) {
        break;
      }
    }

    if (has_any_operators) {
      if (last_non_nested_minus_index == -1 &&
          last_non_nested_plus_index == -1) {
        auto const trimmed_s = [&]() -> std::string_view {
          auto const trimmed_s_begin = std::find_if(
              s.cbegin(), s.cend(), [](char const c) { return c != ' '; });
          auto const trimmed_s_end = std::find_if(
              s.crbegin(), s.crend(), [](char const c) { return c != ' '; });
          return std::string_view(trimmed_s_begin, trimmed_s_end.base());
        }();

        // remove nesting parentheses
        return buildTree(trimmed_s.substr(1, trimmed_s.size() - 2));
      }
      // push minuses down in the tree so they don't multiply too much of the
      // expression by one
      auto const next_operator_index = last_non_nested_plus_index == -1
                                           ? last_non_nested_minus_index
                                           : last_non_nested_plus_index;
      auto const next_operator_it = s.cbegin() + next_operator_index;
      auto* new_node = new Node;
      new_node->op = *next_operator_it;
      new_node->left =
          buildTree(std::string_view(s.cbegin(), next_operator_it));
      new_node->right =
          buildTree(std::string_view(next_operator_it + 1, s.cend()));

      return new_node;
    }
    // number
    auto const number_begins = std::find_if(
        s.cbegin(), s.cend(),
        [](char const c) { return c != '(' && c != ')' && c != ' '; });
    auto const num_parens_to_trim = std::distance(s.cbegin(), number_begins);
    auto trimmed_s_without_opening_parens = s;
    trimmed_s_without_opening_parens.remove_prefix(
        static_cast<size_t>(num_parens_to_trim));
    auto number = 0;
    std::from_chars(trimmed_s_without_opening_parens.data(),
                    trimmed_s_without_opening_parens.data() +
                        trimmed_s_without_opening_parens.size(),
                    number);

    auto* new_node = new Node;
    new_node->number = number;
    return new_node;
  }

  auto reduceTree(Node* const root) -> int {
    if (root == nullptr) {
      // lhs of unary -
      return 0;
    }
    if (root->op == ' ') {
      return root->number;
    }
    auto const left_result = reduceTree(root->left);
    auto const right_result = reduceTree(root->right);
    if (root->op == '+') {
      return left_result + right_result;
    }
    if (root->op == '-') {
      return left_result - right_result;
    }
    assert(false);
    return 0;
  }
};
39368