<p>Given a string <code>s</code> which represents an expression, <em>evaluate this expression and return its value</em>.&nbsp;</p>

<p>The integer division should truncate toward zero.</p>

<p>You may assume that the given expression is always valid. All intermediate results will be in the range of <code>[-2<sup>31</sup>, 2<sup>31</sup> - 1]</code>.</p>

<p><strong>Note:</strong> You are not 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 = "3+2*2"
<strong>Output:</strong> 7
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> s = " 3/2 "
<strong>Output:</strong> 1
</pre><p><strong class="example">Example 3:</strong></p>
<pre><strong>Input:</strong> s = " 3+5 / 2 "
<strong>Output:</strong> 5
</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 integers and operators <code>(&#39;+&#39;, &#39;-&#39;, &#39;*&#39;, &#39;/&#39;)</code> separated by some number of spaces.</li>
	<li><code>s</code> represents <strong>a valid expression</strong>.</li>
	<li>All the integers in the expression are non-negative integers in the range <code>[0, 2<sup>31</sup> - 1]</code>.</li>
	<li>The answer is <strong>guaranteed</strong> to fit in a <strong>32-bit integer</strong>.</li>
</ul>

class Solution {
public:
  set<char> operands{'+', '-', '*', '/'};

  int calculate(string s) {
    int result = 0;
    int temp = 0;
    int operand = 0;
    int index = 0;
    char op = '+';
    for (char c : s) {
      if (c >= '0' && c <= '9') {
        operand = operand * 10 + (c - '0');
      }
      if (operands.contains(c) || index == s.length() - 1) {
        if (op == '+' || op == '-') {
          result += temp;
          temp = op == '+' ? operand : -operand;
        } else if (op == '*') {
          temp *= operand;
        } else if (op == '/') {
          if (temp < 0) {
            temp = -1 * ((double)-temp)/operand;
          } else {
            temp /= operand;
          }
        }
        operand = 0;
        op = c;
      }
      ++index;
    }
    result += temp;
    return result;
  }

  int calculate_fromright(string s) {
    int operand_right = 0;
    bool have_operand_right = false;
    int index = s.length() - 1;
    while (index >= 0) {
      if (!have_operand_right) {
        operand_right = read_operand(s, &index);
      }
      if (index < 0) {
        return operand_right;
      }
      char one_operator = s[index--];
      int operand_left = read_operand(s, &index);
      int result = 0;
      if (one_operator == '+') {
        result = operand_left + operand_right;
      } else if (one_operator == '-') {
        result = operand_left - operand_right;
      } else if (one_operator == '*') {
        result = operand_left * operand_right;
      } else if (one_operator == '/') {
        result = floor((double)operand_left / (double)operand_right);
      }
      operand_right = result;
      have_operand_right = true;
    }
    return operand_right;
  }

private:
  int read_operand(const string& s, int* index) {
    int i = *index;
    long num = 0;
    long multiplier = 1;
    while (i >= 0 && ((s[i] >= '0' && s[i] <= '9') || s[i] == ' ')) {
      if (s[i] == ' ') {
        --i;
      } else {
        num += (s[i--] - '0') * multiplier;
        if (i >= 0) {
          multiplier *= 10;
        }
      }
    }
    *index = i;
    return num;
  }
};
11234