Evaluating a completely parenthesized arithmetic expression I tried to solve the following problem in a programming challenge, but the verdict was time limit exceeded.


  Completely parenthesized expression
  
  Write a program that reads a completely parenthesized expression, and
  prints the result of evaluating it. The three possible operators are
  sum, substraction and multiplication. The operands are natural numbers
  between 0 and 9 (both included).
  
  Input
  
  Input has a completely parenthesized expression. That is, parentheses
  always appear around subexpressions that are not digits. For instance,
  the expression 4 + 3 would be written
  
  ( 4 + 3 )
  
  The expression 8 * (4 + 3) would be written
  
  ( 8 * ( 4 + 3 ) )
  
  The expression (2 − 8) * (4 + 3) would be written
  
  ((2-8)*(4+3))
  
  Output
  
  Print a line with an integer number: the result of evaluating the
  given expression.
  
  (Source: https://jutge.org/problems/P45102_en/statement)


Some of the public test cases were (each line is a different test case):

9
( 3 + 4 )
( 8 * ( 4 + 3 ) )
( ( 2 - 8 ) * ( 4 + 3 ) )
( ( 3 * 2 ) + 1 )


This is my code, which passed every public test cases, but not the private ones. I ask your help in order to find the bottleneck of my program.

#include &lt;iostream&gt;
#include &lt;sstream&gt;

using std::string;
using std::cin;
using std::cout;

/**
 * Returns the evaluation of a completely parenthesed expression.
 * 
 * Preconditions:
 *     * 0 &lt;= i &lt;= j &lt; expr.size()-1.
 *     * expr is a completely parenthesed expression.
 * 
 * Postcondition: returns the evaluation of expr[i..j].
 */

int evaluate(const string&amp; expr, int i, int j)
{
    // Skip leading blanks
    while (expr[i] == ' ') {
        ++i;
    }
    while (expr[j] == ' ') {
        --j;
    }

    // Base case
    if (i == j) {
        return expr[i] - '0';
    }
    // Recursive case
    else {
        // Skip first and last parentheses
        ++i;
        --j;
        int open_parentheses = 0;
        int end_i = i;
        // Loop invariant:
        //     * expr[i..end_i) is part of the first subexpression of expr[i..j]
        //     * open_parentheses is the balance of opened and closed parentheses of expr[i..end_i)
        while (open_parentheses &gt; 0 || (expr[end_i] != '+' &amp;&amp; expr[end_i] != '-' &amp;&amp; expr[end_i] != '*')) {
            if (expr[end_i] == '(') {
                ++open_parentheses;
            }
            else if (expr[end_i] == ')') {
                --open_parentheses;
            }
            ++end_i;
        }
        // Loop ending: expr[end_i] is the 'main' operation of expr[i..j]

        char operation = expr[end_i];

        // By induction hypothesis,
        //     evaluate(expr, i, end_i - 1) 
        // and
        //     evaluate(expr, end_i + 1, j)
        // return the values of the first and the second subexpression of expr[i..j]

        if (operation == '+') {
            return evaluate(expr, i, end_i - 1) + evaluate(expr, end_i + 1, j);
        } else if (operation == '-') {
            return evaluate(expr, i, end_i - 1) - evaluate(expr, end_i + 1, j);
        } else {
            int first_expression = evaluate(expr, i, end_i - 1);
            // Multiplication shortcut
            if (first_expression == 0) {
                return 0;
            } else {
                return first_expression * evaluate(expr, end_i + 1, j);   
            }
        }
    }
}

int main()
{
    string expr;
    getline(cin, expr);
    cout &lt;&lt; evaluate(expr, 0, expr.size() - 1) &lt;&lt; "\n";
}
Use Iterators
The int i and int j are unnecessary parameters in int evaluate(const std::string&amp; expr, int i, int j).
The string class is a standard container class. Standard container classes provide the begin() and
end() functions that provide iterators to the first element and the last element of the container.
This StackOverflow.com Question highlights why iterators are good.

This StackOverflow.com question provides a possible example for finding the last character to process. 

Using iterators will be faster than using indexing by integer. In C++11 or later the following loop
will advance the iterator until non-white space characters are found in the string.

for (auto CharInExperession : exper)
{
    if (!isspace(*CharInExperssion)) {
        break;
    }
}


Use Standard C++ functions to check for white space
In the example above isspace() is used, this checks for all white space, not just space so it checks for
tabs, spaces and new lines. See isspace for information on how to use it. 

Reduce the Complexity of the Code
There is no reason to have the else clause for if(i == j) {, the code in the else clause can be out-dented
because of the return in the if-then portion.