# La función principal de este archivo (de Python) es la función "expr" que determina si una sucesión de símbolos de un lenguaje formal es una expresión y de que tipo. 

# Los distintos símbolos que determinan un lenguaje formal los representaremos en el programa como sigue:

# Variables: x_{i} (i es el índice de la variable y es un número natural)
# Constantes: c_{i} (i es el índice de la constante y es un número natural)
# Relatores: R_{i}^{n} (i es el índice del relator y n es su rango y son números naturales)
# Funtores: f_{i}^{n} (i es el índice del funtor y n es su rango y son números naturales)
# Negador: ~ 
# Implicador: >
# Cuantificador universal: U
# Descriptor: |

## Las siguientes funciones están destinadas a simplificar la notación de las cadenas de signos (pues observese que para determinar si una cadena de signos 
## es una expresión no importa el índice de variables ni constantes, y para los relatores y funtores únicamente importa el rango)

Lan = {"x", "c", "R", "f", "~", ">", "U", "|"}
Form = {"R", "~", ">", "U"}
Term = {"x", "c", "f", "|"}

# Dada una cadena de símbolos sustituye cada variable "x_{i}" por el símbolo "x". Si los símbolos para las variables son incorrectos, es decir,
# no son de la forma "x_{i}" con i un número natural, entonces devuelve como valor 0.
def rep_var(S):
    s = S
    L = []
    init = 0
    while 0 == 0:
        n = s.find("x")
        if n == -1:
            r = S
            for l in L:
                r = r.replace(S[l[0]:l[1]+1],"x",1)
            return(r)
        elif s[n+1] != "_":
            return(0)
        elif s[n+2] != "{":
            return(0)
        else:
            m = s[n+3:].find("}")
            if m == 0 or m == -1:
                return(0)
            elif s[n+3:m+n+3].isdigit():
                L = L + [[init + n,init + m+n+3]]
                s = s[m+n+4:]
                init = init + m + n + 4
            else:
                return(0)

# Dada una cadena de símbolos sustituye cada constante "c_{i}" por el símbolo "c". Si los símbolos para las constantes son incorrectos, es decir,
# no son de la forma "c_{i}" con i un número natural, entonces devuelve como valor 0.
def rep_cons(S):
    s = S
    L = []
    init = 0
    while 0 == 0:
        n = s.find("c")
        if n == -1:
            r = S
            for l in L:
                r = r.replace(S[l[0]:l[1]+1],"c",1)
            return(r)
        elif s[n+1] != "_":
            return(0)
        elif s[n+2] != "{":
            return(0)
        else:
            m = s[n+3:].find("}")
            if m == 0 or m == -1:
                return(0)
            elif s[n+3:m+n+3].isdigit():
                L = L + [[init + n,init + m+n+3]]
                s = s[m+n+4:]
                init = init + m + n + 4
            else:
                return(0)

# Dada una cadena de símbolos sustituye cada relator "R_{i}^{n}" por "Rn". Si los símbolos para los relatores son incorrectos, es decir,
# no son de la forma "R_{i}^{n}" con i, n números naturales, entonces devuelve como valor 0.
def rep_rel(S):
    s = S
    L = []
    init = 0
    while 0 == 0:
        n = s.find("R")
        if n == -1:
            r = S
            for l in L:
                r = r.replace(S[l[0]:l[2]+1],"R"+S[l[1]:l[2]],1)
            return(r)
        elif s[n+1] != "_":
            return(0)
        elif s[n+2] != "{":
            return(0)
        else:
            m = s[n+3:].find("}")
            if m == 0 or m == -1 or s[m+n+4] != "^":
                return(0)
            elif s[n+3:m+n+3].isdigit():
                if s[m+n+5] != "{":
                    return(0)
                else:
                    p = s[m+n+6:].find("}")
                    if p == 0 or p == -1:
                        return(0)
                    elif s[m+n+6:p+n+m+6].isdigit():
                        L = L + [[init + n,init + m+n+6,init + p+m+n+6]]
                        s = s[p+m+n+7:]
                        init = init + p + m + n + 7
                    else:
                        return(0)
            else:
                return(0)

# Dada una cadena de símbolos sustituye cada funtor "f_{i}^{n}" por "fn". Si los símbolos para los relatores son incorrectos, es decir,
# no son de la forma "f_{i}^{n}" con i, n números naturales, entonces devuelve como valor 0.
def rep_fun(S):
    s = S
    L = []
    init = 0
    while 0 == 0:
        n = s.find("f")
        if n == -1:
            r = S
            for l in L:
                r = r.replace(S[l[0]:l[2]+1],"f"+S[l[1]:l[2]],1)
            return(r)
        elif s[n+1] != "_":
            return(0)
        elif s[n+2] != "{":
            return(0)
        else:
            m = s[n+3:].find("}")
            if m == 0 or m == -1 or s[m+n+4] != "^":
                return(0)
            elif s[n+3:m+n+3].isdigit():
                if s[m+n+5] != "{":
                    return(0)
                else:
                    p = s[m+n+6:].find("}")
                    if p == 0 or p == -1:
                        return(0)
                    elif s[m+n+6:p+n+m+6].isdigit():
                        L = L + [[init + n,init + m+n+6,init + p+m+n+6]]
                        s = s[p+m+n+7:]
                        init = init + p + m + n + 7
                    else:
                        return(0)
            else:
                return(0)

Lan = {"x", "c", "R", "f", "~", ">", "U", "|"}
Form = {"R", "~", ">", "U"}
Term = {"x", "c", "f", "|"}

## Simplifica una cadena de símbolos del lenguaje utilizando las funciones anteriores. Si algún símbolo está mal definido (en el sentido explicado para las
## funciones anteriores) o se utiliza algún símbolo que no esté en "Lan" devuelve como valor 0.
def str_simp(s):
    s = rep_var(s)
    if s == 0:
        return(0)
    else:
        s = rep_cons(s)
        if s == 0:
            return(0)
        else:
            s = rep_rel(s)
            if s == 0:
                return(0)
            else:
                s = rep_fun(s)
                if s == 0:
                    return(0)
                else:
                    for a in s:
                        if not (a in Lan or a.isdigit()):
                            return(0)
    return(s)

## Determina si una cadena de símbolos "simplificada" es o no una expresión y, en caso de serlo, si es o no un término.
## Devuelve 0 si la cadena de signos no es una expresión, 1 si es una fórmula y 2 si es un término. 
def expr_simp(r):
    if r == "":
        return(0)
    elif r[0] == "x" or r[0] == "c":
        if len(r) == 1:
            return(2)
        else:
            return(0)
    elif r[0] == "R":
        if len(r) == 1:
            return(0)
        i = 1
        while r[i:i+1].isdigit():
            i = i + 1
        n = int(r[1:i])
        r_aux = r[i:]
        n_aux = n
        while n_aux > 0:
            j = 1
            while expr_simp(r_aux[0:j]) != 2:
                if r_aux[0:j] == r_aux:
                    return(0)
                else: 
                    j = j + 1
            n_aux = n_aux - 1
            r_aux = r_aux[j:]
        if r_aux == "":
            return(1)
        else:
            return(0)
    elif r[0] == "f":
        if len(r) == 1:
            return(0)
        i = 1
        while r[i:i+1].isdigit():
            i = i + 1
        n = int(r[1:i])
        r_aux = r[i:]
        n_aux = n
        while n_aux > 0:
            j = 1
            while expr_simp(r_aux[0:j]) != 2:
                if r_aux[0:j] == r_aux:
                    return(0)
                else: 
                    j = j + 1
            n_aux = n_aux - 1
            r_aux = r_aux[j:]
        if r_aux == "":
            return(2)
        else:
            return(0)
    elif r[0] == "~":
        return(expr_simp(r[1:]))
    elif r[0] == ">":
        if len(r) == 1:
            return(0)
        n = 2
        r_aux = r[1:]
        while n > 0:
            j = 1
            while expr_simp(r_aux[0:j]) != 1:
                if r_aux[0:j] == r_aux:
                    return(0)
                else: 
                    j = j + 1
            n = n - 1
            r_aux = r_aux[j:]
        if r_aux == "":
            return(1)
        else:
            return(0)
    elif r[0] == "U":
        if len(r) == 1 or len(r) == 2:
            return(0)
        elif r[1] != "x":
            return(0)
        else:
            if expr_simp(r[2:]) == 1:
                return(1)
            else:
                return(0)
    elif r[0] == "|":
        if len(r) == 1 or len(r) == 2:
            return(0)
        elif r[1] != "x":
            return(0)
        else:
            if expr_simp(r[2:]) == 1:
                return(2)
            else:
                return(0)
    else:
        return(0)

## Determina si una sucesión de signos dada es o no una expresión y, en caso de serlo, si es o no un término.
## Devuelve -1 si los símbolos de la cadena no son correctos (en el sentido dicho en los programas anteriores), 0 si la cadena de signos
## no es una expresión, 1 si es una fórmula y 2 si es un término. 
def expr(s):
    if str_simp(s) != 0:
        return(expr_simp(str_simp(s)))
    else:
        return(-1)

s = "Ux_{1}Ux_{23}R_{0}^{2}f_{0}^{2}x_{1}f_{0}^{1}x_{23}f_{0}^{1}f_{0}^{2}x_{1}x_{23}"
print(expr(s))