Recur16. Вывести значение целочисленного выражения, заданного в виде строки S. Выражение определяется следующим образом:
<выражение> ::= <терм> | <выражение> + <терм> |
<выражение> - <терм>
<терм> ::= <элемент> | <терм> * <элемент>
<элемент> ::= <цифра> | (<выражение>)

Решение на Python 3:

import random
import string
import numpy as np

def RndTerm():
    N = random.randrange(1,5)
    lst_digit = [str(random.randrange(0,10)) for i in range(0,N)]
    lst_oper = ['*']*(N-1)
    result = [None]*(2*N - 1)
    result[::2] = lst_digit
    result[1::2] = lst_oper
    return "".join(result)

def RndExpr():
    N = random.randrange(1,5)
    lst_expr1 = [RndTerm() for i in range(0,N)]
    N = random.randrange(0,5)
    lst_expr2 = [RndExprBrackets() for i in range(0,N)]
    lst_expr = lst_expr1 + lst_expr2
    random.shuffle(lst_expr)
    N = len(lst_expr)
    lst_oper = list(np.random.choice(['+','-'], N-1))
    result = [None]*(2*N - 1)
    result[::2] = lst_expr
    result[1::2] = lst_oper
    return "".join(result)

def RndExprBrackets():
    N = random.randrange(2,5)
    lst_term = [RndTerm() for i in range(0,N)]
    lst_oper = list(np.random.choice(['+','-'], N-1))
    result = [None]*(2*N - 1)
    result[::2] = lst_term
    result[1::2] = lst_oper
    return "("+"".join(result)+")"

def CalcTerm(S):
    #print(S)
    n = len(S)
    if n > 1:
        oper = S[n-2]
        if oper == "+" or oper == "-":
            return 1
        x = int(S[n-1])
        return CalcTerm(S[:-2]) * x
    return int(S[0])

def CalcExpr(S):
    print(S)
    idx_plus = S.rfind('+')
    idx_minus = S.rfind('-')
    idx_bracket_close = S.rfind(')')
    #print("+:",S.rfind('+'),"; -:",S.rfind('-'))
    s_expr = ""
    s_term = ""
    sign = 1
    if idx_plus == -1 and idx_minus == -1 \
       and idx_bracket_close == -1:
        s_term = S
    elif idx_bracket_close > idx_plus and idx_bracket_close > idx_minus:
        idx_bracket_open = S.rfind('(')
        s_expr = S[:idx_bracket_open-1]
        s_expr2 = S[idx_bracket_open:idx_bracket_close]
        if S[idx_bracket_open-1] == "+":
            sign = 1
        else:
            sign = -1
        return CalcExpr(s_expr) + sign*CalcExpr(s_expr2)
    elif idx_plus > idx_minus:
        s_expr = S[:idx_plus]
        s_term = S[idx_plus+1:]
        sign = 1
    else:
        s_expr = S[:idx_minus]
        s_term = S[idx_minus+1:]
        sign = -1
    #print(s_expr,":",s_term,":",sign)

    if len(s_expr) > 0:
        return CalcExpr(s_expr) + sign*CalcTerm(s_term)
    else:
        return CalcTerm(s_term)

for i in range(0,5):
    s = RndExpr()
    print()
    #   print(s)
    print(s, "=" ,eval(s))
    print(s, "=" ,CalcExpr(s))