Evaluating a completely parenthesized arithmetic expression

Question

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 <iostream>
#include <sstream>

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

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

int evaluate(const string& 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 > 0 || (expr[end_i] != '+' && expr[end_i] != '-' && 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 << evaluate(expr, 0, expr.size() - 1) << "\n";
}

Answer 1

Use Iterators
The int i and int j are unnecessary parameters in int evaluate(const std::string& 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.

Answer 2

I got a pass verdict with the following code.

Some comments:

• Moved from ints to string::const_iterators. Inefficiency was here.
• Didn't move to isspace. I'm sure it is a better option if efficiency is not that important, but failed in efficiency terms.
• I've simplified the recursion decision block.

The code:

#include <iostream>
#include <sstream>

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

typedef string::const_iterator it;


/**
 * Returns the evaluation of a completely parenthesed expression.
 * 
 * Preconditions:
 *     * i and j point to characters of expr.
 *     * expr is a completely parenthesed expression.
 * 
 * Postcondition: returns the evaluation of expr[i..j].
 */
int evaluate(const string& expr, it i, it j)
{
    // Skip leading blanks
    while (*i == ' ') {
        ++i;
    }
    while (*j == ' ') {
        --j;
    }

    // Base case
    if (i == j) {
        return *i - '0';
    }

    // Recursive case
    // Skip first and last parentheses
    ++i;
    --j;
    int open_parentheses = 0;
    it 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 > 0 || (*end_i != '+' && *end_i != '-' && *end_i != '*')) {
        if (*end_i == '(') {
            ++open_parentheses;
        }
        else if (*end_i == ')') {
            --open_parentheses;
        }
        ++end_i;
    }
    // Loop ending: *end_i is the 'main' operation of expr[i..j]

    char operation = *end_i;

    it begin_j = end_i;
    ++begin_j;
    --end_i;
    int first = evaluate(expr, i, end_i);
    if (operation == '*') {
        if (first == 0) {
            return 0;
        } else {
            int second = evaluate(expr, begin_j, j);
            return first * second;   
        }
    } else {
        int second = evaluate(expr, begin_j, j);
        if (operation == '+') {
            return first + second;
        } else {
            return first - second;
        }
    }
}


int main()
{
    string expr;
    getline(cin, expr);
    it i, j;
    i = expr.begin();
    j = expr.end();
    --j;
    cout << evaluate(expr, i, j) << "\n";
}