Expression Evaluator

A Researcher has introduced a special type of mathematical expression as a part of one of his research. He has several numbers of, randomly generated expressions that he wanted to evaluate. But because of his buggy generation algorithm, those expressions can have invalid syntax. As a programmer, he has been asked you to help to test those algorithms.

You have to write a correct algorithm to evaluate the given list of expressions. If the expression is invalid you have to show the message "invalid" otherwise the value of the result.

The grammar of the expressions is explained below.

An expression can contain several numbers of binary operations, integers, parenthesis. The operators are given below,

Addition +, Difference -
Multiplication *,
Minimum %, Maximum @

Operators are ordered according to their precedence. +,- have same precedence. %,@ have the hightest precedence among all operators. Other than this expression inside the paranthesis should be evaluated first.

To avoid conflicts If there are multiple operation with same precedence following decisions should be taken,

if there are multiple aditions, differences; then among them left most operator should be evaluated first.
if there are mutiple minimum, maximum operators; then among them the right most operator should be evaluated first.

Also there are some guidelines to follow,

All the operation are binary operations. There cannot be unary operation such as negative or positive.
It is guarenteed that the input expression does not contains any character other than these digit, +, -, *,%, @, (, ).
The - operator is special because it always results a positive value. As an example imagine that a-b is there and a < b then answer must be b-a.
Integers cannot be start with zero if there is integers start with zero then the expression is invalid.
Expression cannot be empty.
%, @ operators results minimum and maximum respectively. As an example 45%32 will give 32; 43%43 will give 43.

In addition following are the set grammar rules given by the reaseacher,

E -> E + T | E - T | T
T -> T * F | F
F -> P % F | P @ F | P
P -> (E) | D
D -> Integer

Input Format

first line contains integer N the number of test cases. Then N lines after that contains an expression which needs to be evaluated.

N
exp1
exp2
...
expN

Constraints

Output Format

N number of lines. If the ith expression is valid there should be value of the expression. Otherwise the text invalid.

val1
val2
invalid
val3
..
valN

Sample Input 0

3
1*2-4-1
3-4*4
(4-5)*3(3)

Sample Output 0

1
13
invalid

Explanation 0

Expression 1

1*2-4-1 => 2-4-1 // * has highest precedence
2-4-1   => 2-1   // left most - has highest precedence 2-4 = 2
2-1     => 1

Expression 3

(4-5)*3(3)
|
should be an operator

Sample Input 1

4
2@4%1
4-3-1
(2-2-2)@
()

Sample Output 1

2
0
invalid
invalid

Explanation 1

Expression 1

2@4%1 => 2@1   // right most operator has highest precedence
2@1   => 2

Solution

Partially working solution (Python)

By Suhas Dissanayake

def mi(a,b):
    return a if a<b else b

def ma(a,b):
    return a if a>b else b

def is_bop(op):
     return op in {"+", "-", "*", "@", "%"}

def tokenize(st):
    tokens = []
    i = 0

    while(i < len(st)):
        if st[i].isdigit():
            s = ""
            while i<len(st) and st[i].isdigit():
                s += st[i]
                i += 1
            tokens.append(int(s))
        elif st[i] == "(":
            ob = 0
            s = ""
            i+=1
            while i<len(st):
                if st[i] == ")":
                    if ob == 0:
                        i+=1
                        break
                    elif ob > 0:
                        ob -= 1
                        s += st[i]
                    else:
                        return []
                elif st[i] == "(":
                    ob += 1
                    s += st[i]
                else:
                    s += st[i]
                i += 1
            tt = tokenize(s)
            tokens.append(tt)

        else:
            tokens.append(st[i])
            i+=1
    return tokens

def evaluate(tokens):
    if isinstance(tokens, int):
        return tokens

    if isinstance(tokens,list) and len(tokens) == 1:
        return evaluate(tokens[0])

    if not isinstance(tokens, list) or len(tokens) != 3:
        return "invalid"

    left, op, right = tokens

    if not is_bop(op):
        return "invalid"

    l_eval = evaluate(left)
    r_eval = evaluate(right)

    if l_eval == "invalid" or r_eval == "invalid":
        return "invalid"

    match op:
        case "+":
            return l_eval + r_eval
        case "-":
            return abs(l_eval - r_eval)
        case "*":
            return l_eval * r_eval
        case "@":
            return ma(l_eval,r_eval)
        case "%":
            return mi(l_eval,r_eval)

def prioritize(tokens):
    if isinstance(tokens,int):
        return tokens
    if len(tokens) <= 3:
        return tokens

    i = len(tokens) - 1;
    while i > 0:
        if tokens[i] == "%" or tokens[i] == "@":
            pr = i - 1
            ne = i + 1
            if pr < 0 or ne >= len(tokens):
                return "invalid"
            if isinstance(tokens[pr],str) or isinstance(tokens[ne],str):
                return "invalid"

            group = [prioritize(tokens[pr]),tokens[i],prioritize(tokens[ne])]
            tokens[ne] = group
            del tokens[pr]
            del tokens[pr]
            i -= 1
        i -= 1

    i = 0;
    while i<len(tokens):
        if tokens[i] == "*":
            pr = i - 1
            ne = i + 1
            if pr < 0 or ne >= len(tokens):
                return "invalid"
            if isinstance(tokens[pr],str) or isinstance(tokens[ne],str):
                return "invalid"

            group = [prioritize(tokens[pr]),tokens[i],prioritize(tokens[ne])]
            tokens[ne] = group
            del tokens[pr]
            del tokens[pr]
            i -= 1
        i += 1

    i = 0;
    while i<len(tokens):
        if tokens[i] == "-" or tokens[i] == "+":
            pr = i - 1
            ne = i + 1
            if pr < 0 or ne >= len(tokens):
                return "invalid"
            if isinstance(tokens[pr],str) or isinstance(tokens[ne],str):
                return "invalid"

            group = [prioritize(tokens[pr]),tokens[i],prioritize(tokens[ne])]
            tokens[ne] = group
            del tokens[pr]
            del tokens[pr]
            i -= 1
        i += 1

    return tokens


count = int(input())
for i in range(count):
    exp = input()
    tokens = tokenize(exp)
    pri = prioritize(tokens)
    if pri == "invalid":
        print("invalid")
    else:
        ans = evaluate(pri)
        print(ans)