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.
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";
}