15. CORRECT EXPRESSION - TASK SOLUTION



In this task, your goal is to check whether a mathematical expression is correct by placing the operators between the numbers properly. The task leads you through the challenge of building correct arithmetic operations in a sequence, using logical variables and carefully taking care of the order of operations.

On this page we give two different approaches to solving this problem, each with a detailed explanation and accompanying code. The first approach focuses on a simpler implementation, while the second uses more structured code to solve the task more efficiently. The goal is to show you different ways to approach one problem and to encourage you to experiment with your own solutions.

Below, read the task, and then explore the solutions, which are given with explanations of every step.



Task text


/*
In the expression a_b_c=d, two arithmetic operations should be inserted instead of the underscores so that the expression is correct.
The operations that can be used are addition (+), subtraction (−), multiplication (∗) and integer division (/).
The standard precedence of arithmetic operations applies.

Input:
Each of the four lines of standard input contains one integer (a, b, c and d, in that order).
All numbers are in the range [1,1000].

Output:
Print all possible solutions to standard output (in any order), each in a separate line.
One solution is printed as 2 characters (separated by a space) that represent the arithmetic operations
which must be inserted in that order for the expression to be correct.
If it is not possible to get a correct expression, print "impossible".

Example 1:
Input:
2
3
4
2

Output:
* -
+ /
- /

Explanation:
* - is a solution because 2 * 3 - 4 = 2
+ / is a solution because 2 + 3 / 4 = 2  (integer division has higher precedence)
- / is a solution because 2 - 3 / 4 = 2  (integer division has higher precedence)

Example 2:
Input:
8
3
2
12

Output:
* /

Example 3:
Input:
2
2
9
3

Output:
impossible
*/


Solution

After reading the values of a, b, c and d, the program changes the possible operations using two for loops, combining the four basic arithmetic operations. The first loop chooses the first operation (between a and b), and the second one chooses the second operation (between b and c). Using switch statements and logical variables (later, minus, impossible), the program applies the precedence of operations correctly and finds all combinations that give the correct result.




#include <iostream>
using namespace std;

int main() {
    int a, b, c, d, r;
    bool impossible = true;
    cin >> a >> b >> c >> d;
    char x, y;
    x = '+';
    y = '+';
    r = a;

    for (int i = 0; i < 4; i++) {
        bool later = false;
        bool minus = false;
        int rMinus = a;

        switch (i) {
            case 0: x = '+'; later = true; r = 0; break;
            case 1: x = '-'; later = true; r = 0; minus = true; break;
            case 2: r = a * b; x = '*'; break;
            case 3: r = a / b; x = '/'; break;
        }

        int r1 = r;
        bool later2 = later;

        for (int j = 0; j < 4; j++) {
            switch (j) {
                case 0:
                    if (minus) later2 = false;
                    if (later2) r = b + c;
                    else if (minus) r = rMinus - b + c;
                    else r = r + c;
                    y = '+';
                    break;
                case 1:
                    if (minus) later2 = false;
                    if (later2) r = b - c;
                    else if (minus) r = rMinus - b - c;
                    else r = r - c;
                    y = '-';
                    break;
                case 2:
                    y = '*';
                    if (later2) r = b * c;
                    else r = r * c;
                    break;
                case 3:
                    y = '/';
                    if (later2) r = b / c;
                    else r = r / c;
                    break;
            }

            if (later2 && x == '+') r = a + r;
            else if (later2 && x == '-') r = a - r;

            if (r == d) {
                cout << x << " " << y << endl;
                impossible = false;
            }

            r = r1;
            later2 = later;
        }
        r = a;
    }

    if (impossible)
        cout << "impossible" << endl;

    return 0;
}


Explanation of the solution

This solution uses a combination of for loops and switch statements to generate all possible combinations of two arithmetic operations between the numbers a, b and c in order to get the given result d.

1. Reading the data:
The program reads the numbers a, b, c and d and sets the variable impossible to true. If it does not find any solution, it prints "impossible" at the end.

2. The first for loop:
Chooses the first operation between a and b. If it is + or -, the computation is postponed because of precedence, while * and / are computed immediately.

3. The second for loop:
Chooses the second operation between b and c and computes the result according to the previous operation.

4. Applying the first operation afterwards:
If the first operation is + or -, it is executed after the second one has finished. This respects the mathematical precedence of operations.

5. Checking the solution:
If the result equals the given value d, the operations are printed. If no combination matches, "impossible" is printed.


Conclusion:
This solution is efficient and clear because it checks all combinations of arithmetic operations and respects the order in which they are executed. Thanks to the logical variables, the program clearly distinguishes the situations in which the first operation must be executed afterwards.

Explanation of the task



This solution uses a combination of for loops and switch statements to generate all possible combinations of two arithmetic operations that could connect the numbers a, b, c so that we get the given result d. Here is a detailed explanation of the key parts:

1. Reading the data


int a,b,c,d,r;
bool impossible=true;
cin >> a >> b >> c >> d;
char x, y;
r = a;
  

First the numbers a, b, c and d are read, and impossible is a logical variable that tracks whether a solution can be found. If we find no solution, at the end of the program we print "impossible".

2. The first for loop (choosing the first operation)


for(int i=0; i<4; i++)
{
    // Switch that changes the first operation: '+', '-', '*', '/'
    switch(i)
    {
        case 0: x = '+'; later = true; r = 0; break;
        case 1: x = '-'; later = true; r = 0; minus = true; break;
        case 2: r = a * b; x = '*'; break;
        case 3: r = a / b; x = '/'; break;
    }
}
  

This loop goes through all four possible operations for the first part of the expression (a operation1 b). The operations are addition (+), subtraction (-), multiplication (*) and division (/). If the first operation is + or -, the result is not computed immediately because of operator precedence, and this is marked with the variable later. If the operation is multiplication or division, the result is computed immediately.

3. The second for loop (choosing the second operation)


for(int j=0; j<4; j++)
{
    switch(j)
    {
        case 0: r = b + c; y = '+'; break;
        case 1: r = b - c; y = '-'; break;
        case 2: r = b * c; y = '*'; break;
        case 3: r = b / c; y = '/'; break;
    }
}
  

The second loop tests all possible operations for the second part of the expression (operation2 c). Again the same four operations are used: +, -, *, and /. These operations are applied to the previous result (or to b if the first operation is + or -).

4. Applying the first operation afterwards


if(later2 && x == '+') r = a + r;
else if(later2 && x == '-') r = a - r;
  

If the first operation has lower precedence (i.e. if it is + or -), it is applied afterwards to the result of the second operation. If the first operation was -, the subtraction must be done at the end, after the second operation.

5. Checking and printing the result


if(r == d)
{
    cout << x << " " << y << endl;
    impossible = false;
}
  

If the result equals the given number d, the program prints the operations that led to the correct result. If no combination of operations gave the correct result, "impossible" is printed at the end of the program.

Important notes:

  • Operator precedence: Addition and subtraction have lower precedence than multiplication and division. That is why addition or subtraction is applied afterwards if it comes first in the expression.
  • Integer division: The results of division are integers, i.e. rounded down to the lower integer.

Conclusion:

This solution is efficient because it covers all combinations of operations and takes care of operator precedence. The program checks all possible operations for the first and the second operand, and then checks whether the combination gives the required result. If no combination is correct, the program prints "impossible".

Comment on the solution

The solution shows practical knowledge of C++, especially in combining for loops and switch statements to generate all possible combinations of arithmetic operations. Logical variables such as later and minus make it possible to respect operator precedence correctly, which shows an understanding of basic mathematical rules in a programming context.

The efficiency of the solution is good for the given range of numbers, because all four basic operations are tested systematically. However, the code is rather procedural and somewhat long because of the many switch cases, which makes it harder to maintain and read. For bigger tasks or extended functionality, you could consider using a table of operations or functions for evaluating expressions to reduce code duplication.

In addition, solving the task requires a good understanding of integer division and operator precedence, which gives good insight into logical thinking and managing control flow. Readers can see how a combination of simple control flow and arithmetic can solve a complex problem, but also where the code could be improved in terms of modularity and readability.

Possible improvements

  • Using functions or lambda expressions to evaluate expressions in order to reduce code duplication.
  • Replacing the switch statements with a structured approach, e.g. using a table of operations or an array of functions.
  • Improving readability and maintainability of the code through modularization and clearer variable names.
  • Adding a check for division by zero to avoid errors in integer division.
  • The possibility of extending to more operations or numbers using recursion or a combination generator.

Solution 2 - Correct expression

This task consists of examining different combinations of mathematical operations that can be placed between three numbers in order to get the required value. Using the four basic operations (+, -, *, /) and their precedence, we need to find all valid combinations that satisfy the expression.

The input contains four numbers a, b, c and d, where the expression a ? b ? c = d should be correct. Operator precedence must be respected, i.e. multiplication and division have higher precedence than addition and subtraction. We need to examine all possible combinations of operations and compute them to see whether they give the required result.

Code:


#include <iostream>
using namespace std;

// Function that computes the result of the expression with the given operations
int calculate(int a, int b, int c, char op1, char op2) {
    int result;
    if (op1 == '*' || op1 == '/') {
        if (op1 == '*') result = a * b;
        else if (op1 == '/') result = a / b;
        // After computing a op1 b, we apply op2 with c
        if (op2 == '+') result += c;
        else if (op2 == '-') result -= c;
        else if (op2 == '*') result *= c;
        else if (op2 == '/') result /= c;
    } else {
        // If op1 is + or -, we first compute a op1 b, then op2 with c
        if (op1 == '+') result = a + b;
        else if (op1 == '-') result = a - b;
        if (op2 == '*') result *= c;
        else if (op2 == '/') result /= c;
        else if (op2 == '+') result += c;
        else if (op2 == '-') result -= c;
    }
    return result;
}

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;

    char operators[] = {'+', '-', '*', '/'};
    bool found = false;

    // We examine all combinations of two operations
    for (char op1 : operators) {
        for (char op2 : operators) {
            // Avoid division by zero
            if ((op1 == '/' && b == 0) || (op2 == '/' && c == 0)) continue;

            int result = calculate(a, b, c, op1, op2);
            if (result == d) {
                cout << op1 << " " << op2 << endl;
                found = true;
            }
        }
    }

    if (!found) {
        cout << "impossible" << endl;
    }

    return 0;
}
    

Note: when the first operation is + or - and the second is * or /, the function calculate computes (a op1 b) op2 c, so it does not respect operator precedence in that case. For example 1 (2, 3, 4, 2) this program prints only * -. Try to fix the function so that it computes a op1 (b op2 c) in that case – Solution 3 below shows how.

Explanation:

  • Input data: The program reads four numbers: a, b, c and d.
  • Operators: The operators used are addition (+), subtraction (-), multiplication (*) and integer division (/). We combine two operations between a, b and c.
  • Division check: If one of the operands in a division is 0, we skip that case to avoid an error.
  • Computation: Using the function calculate, we check the result for all combinations of operators and test whether the result equals d.
  • Output: If we find a valid combination, we print the operators, and if we find none, we print "impossible".

Comment on the solution:

This solution is readable and modular, because it uses the function calculate to evaluate the expression, which reduces code duplication. Examining all combinations of operations with for loops is simple and logical, and the division-by-zero check adds safety.

The efficiency is good for the given range of numbers, and the code is easier to maintain than the first version with switch statements. Operator precedence is handled inside the function calculate, which shows how mathematical rules and control-flow logic can be combined.

Possible improvements include:

  • Further modularization, e.g. creating a function that generates all combinations of operators.
  • Using recursion or a backtracking approach for a more flexible extension to more operators or numbers.
  • Extending the validity check of the expression to cover cases of integer division with a remainder and larger numbers.

Solution 3 - Correct expression (recursion / backtracking, respecting operator precedence)

The input contains four integers a, b, c and d. We need to check whether there is a choice of two operations op1 and op2 from the set +, -, *, / so that the expression a op1 b op2 c = d is correct. If there is a solution, the corresponding expression is printed (e.g. 1+2*3=7), and if there is no solution, No solution is printed.

The idea of this version is to generate all combinations of two operators recursively (backtracking approach), and now operator precedence is taken into account. If the second operator has higher precedence than the first one, the expression in brackets (b op2 c) is computed first. Otherwise, the computation goes in order (a op1 b) op2 c.

Code:


#include <iostream>
#include <vector>
#include <utility>

using namespace std;

// applyOp: performs the operation x op y, returns pair(valid, value)
pair<bool, long long> applyOp(long long x, char op, long long y) {
    if (op == '+') return {true, x + y};
    if (op == '-') return {true, x - y};
    if (op == '*') return {true, x * y};

    if (op == '/') {
        // protection: division by zero
        if (y == 0) return {false, 0};
        // we require exact integer division without a remainder
        if (x % y != 0) return {false, 0};
        return {true, x / y};
    }

    return {false, 0}; // unknown operator
}

// operator precedence
int priority(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;
}

vector<char> ops = { '+', '-', '*', '/' };
bool found = false;
vector<char> chosen(2);

// dfs chooses the operators recursively
void dfs(int pos, long long a, long long b, long long c, long long d) {
    if (found) return; // stop if a solution has already been found

    if (pos == 2) {
        if (priority(chosen[0]) >= priority(chosen[1])) {
            // (a op1 b) op2 c
            auto p1 = applyOp(a, chosen[0], b);
            if (!p1.first) return;
            auto p2 = applyOp(p1.second, chosen[1], c);
            if (!p2.first) return;

            if (p2.second == d) {
                cout << a << chosen[0] << b << chosen[1] << c << "=" << d << '\n';
                found = true;
            }
        } else {
            // a op1 (b op2 c)
            auto p3 = applyOp(b, chosen[1], c);
            if (!p3.first) return;
            auto p4 = applyOp(a, chosen[0], p3.second);
            if (!p4.first) return;

            if (p4.second == d) {
                cout << a << chosen[0] << "(" << b << chosen[1] << c << ")" << "=" << d << '\n';
                found = true;
            }
        }
        return;
    }

    for (char o : ops) {
        chosen[pos] = o;
        dfs(pos + 1, a, b, c, d);
        if (found) return;
    }
}

int main() {
    long long a, b, c, d;
    if (!(cin >> a >> b >> c >> d)) return 0;

    dfs(0, a, b, c, d);

    if (!found) cout << "No solution" << '\n';

    return 0;
}
    

Explanation:

Input data: The program reads four numbers: a, b, c, and d.
Operators: addition (+), subtraction (-), multiplication (*), and integer division (/).
Operator precedence: if the second operator has higher precedence (e.g. * takes precedence over +), the part in brackets is computed first.
Division check: in the case of division by zero or a non-integer result, the expression is skipped.
Output: if there is a combination of operators that gives the correct result, the expression is printed; if not, No solution is printed.

Comment on the solution:

This version uses recursion and a clear division of cases based on operator precedence. This gives behaviour identical to the mathematical rules for evaluating expressions in C++. The code is readable and precisely separates the logic for situations with and without brackets, which avoids repeated computation and unnecessary combinations.

Possible improvements:

  • Extending to more operators and operands with recursive handling of precedence.
  • Storing all possible correct expressions instead of only the first one.
  • Adding automatic formatting of the expression for clearer output.

​Back
​|<Qualifications for district competitions