计算一个完全带括号的算术表达式

Question

我试图在编程挑战中解决以下问题，但结果超过了时间限制。

完全带括号的表达式编写一个程序，该程序读取一个完全带括号的表达式，并打印计算结果。这三种可能的运算符是和、减和乘。操作数是0到9之间的自然数(都包括在内)。输入输入有一个完全带括号的表达式。也就是说，括号总是出现在不是数字的子表达式的周围。例如，表达式4 + 3将写入( 4 + 3 )表达式8 * (4 + 3)将写入( 8 * ( 4 + 3 ) )表达式(2 − 8) * (4 + 3)将写入((2-8)*(4+3))输出用整数打印一行:计算给定表达式的结果。(资料来源：https://jutge.org/problems/P45102_en/陈述)

一些公共测试用例是(每一行都是不同的测试用例)：

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

这是我的代码，它通过了每个公共测试用例，但不是私有测试用例。为了找出我节目的瓶颈，我请求你的帮助。

#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

我得到了以下代码的通过率。

一些评论：

• 从ints搬到了string::const_iterators，效率低下。
• 没有搬到isspace。我相信，如果效率不是那么重要，但在效率方面却失败了，那将是一个更好的选择。
• 我简化了递归决策块。

守则：

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