<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 <cctype>
#include <memory>
#include <pstl/glue_algorithm_defs.h>
#include <stack>
#include <stdexcept>
#include <string>
#include <utility>

using namespace std;

class Expr {
public:
  virtual int eval() const = 0;
  // define descructor since its relied upon by unique_ptr
  virtual ~Expr() = default;
};

class Constant : public Expr {
  int value;

public:
  Constant(int value) : value(value){};
  virtual int eval() const { return value; }
};

using ExprPtr = unique_ptr<Expr>;

class UnaryMinus : public Expr {
  ExprPtr operand;

public:
  UnaryMinus(ExprPtr operand) : operand(std::move(operand)) {}
  virtual int eval() const { return -operand->eval(); }
};

class Binary : public Expr {
  char op;
  ExprPtr left;
  ExprPtr right;

public:
  Binary(char op, ExprPtr left, ExprPtr right)
      : op(op), left(std::move(left)), right(std::move(right)) {}
  virtual int eval() const {
    switch (op) {
    case '+':
      return left->eval() + right->eval();
    case '-':
      return left->eval() - right->eval();
    }
    throw invalid_argument("bad op");
  }
};

class Solution {
public:
  int precedence(char op) {
    switch (op) {
    case '+':
    case '-':
    case '_':
      return 1;
    default:
      return 0;
    }
  }

  /* Parse the operator op using the given operands */
  void parseOp(char op, stack<ExprPtr> &operands) {
    if (op == '(')
      return;
    if (op == '_') {
      ExprPtr operand = std::move(operands.top());
      operands.pop();
      operands.push(make_unique<UnaryMinus>(std::move(operand)));
      return;
    }
    // binary operator
    ExprPtr right = std::move(operands.top());
    operands.pop();
    ExprPtr left = std::move(operands.top());
    operands.pop();
    operands.push(make_unique<Binary>(op, std::move(left), std::move(right)));
  }

  /* Parse the given infix into an expression for evaluation */
  ExprPtr parse(string s) {
    stack<ExprPtr> operands;
    stack<char> ops;
    string operand = "";

    // remove whitespace from string
    s.erase(remove(s.begin(), s.end(), ' '), s.end());

    for (int i = 0; i < s.size(); i++) {
      char c = s[i];
      if (isdigit(c)) {
        operand += c;
        continue;
      }
      // not an operand: parse any existing operand we are building
      if (operand.size() > 0) {
        operands.push(make_unique<Constant>(stoi(operand)));
        operand = "";
      }
      // c must be an operator
      if (c == '-' && (i <= 0 || s[i - 1] == '(')) {
        // unary minius: parse as underscore
        ops.push('_');
        continue;
      }
      if (c == '(') {
        ops.push('(');
        continue;
      }
      if (c == ')') {
        // parse until prior '('
        while (ops.top() != '(') {
          parseOp(ops.top(), operands);
          ops.pop();
        }
        // remove '('
        ops.pop();
        continue;
      }
      // evaluate any outstanding operators
      while (ops.size() > 0 && precedence(c) <= precedence(ops.top())) {
        parseOp(ops.top(), operands);
        ops.pop();
      }
      ops.push(c);
    }

    // parse any remaining operands & operators
    if (operand.size() > 0) {
      operands.push(make_unique<Constant>(stoi(operand)));
    }
    while (ops.size() > 0) {
      parseOp(ops.top(), operands);
      ops.pop();
    }

    return std::move(operands.top());
  }

  int calculate(string s) { return parse(s)->eval(); }
};


32806