## Description

COSC 326

Arithmetic

A common sort of puzzle or problem one sees in newspapers, particularly at the beginning of each year goes along the lines of “make up a formula whose value is 2022,

using the numbers 1 through 10 in that order”. Of course the rules of the game are

never entirely clear – in particular whether brackets are allowed, and what operations

are permissible.

In this étude we’ll look at a simplified model. The only operations allowed are + and

× and brackets are not permitted. However, we’ll consider both ‘proper’ order of operations where

1 + 2 × 3 = 7

and ‘left to right’ where

1 + 2 × 3 =LR 9.

Task

Input from stdin will be a sequence of scenarios. Each scenario is one line of the form:

the letter N or L, a positive integer (target value) and a sequence of positive integers

(numbers to be used). There are no blank lines separating scenarios. Note that the

numbers are to be used exactly in the order given.

The output, to stdout for a properly-formatted scenario should be the character representing the order of operations used, then the target value, an equals sign, and finally

an expression of the required value (using the character * for multiplication, and with

spaces before and after each operation and the equals sign), or the word impossible.

If a scenario is improperly formatted then the output should be <in> Invalid where

<in> is the input line.

Example

Input:

N 7 1 2 3

L 9 1 2 3

N 100 2 3 5

X 2 1 2

Output:

N 7 = 1 + 2 * 3

L 9 = 1 + 2 * 3

N 100 2 3 5 impossible

X 2 1 2 Invalid

Relates to Objectives

2.1, 2.2, 2.3, 2.5, 2.10, 3.4, 3.5, 3.7

COSC 326 2022 Summer School Étude 9

(1 point, Individual)