-- ============================================================
-- ExprTree — árbol binario de SINTAXIS para expresiones
-- aritméticas con los operadores  +  -  *  /  **  (versión didáctica).
--
-- Es un AST (Abstract Syntax Tree): un árbol binario donde
--   * las HOJAS llevan un operando  (p.ej. "a", "b", "3");
--   * los nodos INTERNOS llevan un operador  ("+","-","*","/","**")
--     y tienen exactamente dos subárboles.
--
-- El operador "**" es la POTENCIA: node("**", b, e) representa
-- la expresión  b elevado a e  (p.ej. (a**b) = a^b). Es binario,
-- como los otros cuatro, así que encaja sin cambiar la estructura.
--
-- Una expresión aritmética TOTALMENTE PARENTIZADA se corresponde
-- 1 a 1 con un ExprTree. Por ejemplo  ((a+b)*c)/(c+d)  es:
--
--   node("/",
--        node("*", node("+", leaf("a"), leaf("b")), leaf("c")),
--        node("+", leaf("c"), leaf("d")))
--
-- ── Diseño ──────────────────────────────────────────────────
-- ExprTree HEREDA de BTree (árbol binario genérico): reusa los
-- constructores BTree_Empty / BTree_Create y los observadores
-- BTree_Root / BTree_Left / BTree_Right / BTree_IsEmpty.
-- La etiqueta de cada nodo es un String.
--
-- Simplificaciones respecto de un AST "completo":
--   * la etiqueta es String (no una clase ExprNode aparte);
--   * un único constructor de nodo interno, node(símbolo,izq,der),
--     en vez de cinco: el símbolo es el operador. La precondición
--     de `node` obliga a que el símbolo sea uno de + - * / ** ;
--   * sin evaluación numérica (los operandos son simbólicos);
--     `render` reconstruye el string parentizado, que es lo que
--     evidencia la correspondencia árbol <-> expresión.
--
-- Nota: BTree se incluye aquí mismo (igual que en BSTree.nereus
-- y BTreeWithSize.nereus) para que el archivo sea autocontenido.
-- ============================================================

CLASS BTree [elem]
BASIC CONSTRUCTORS BTree_Empty, BTree_Create
EFFECTIVE
TYPE BTree
OPERATIONS
  BTree_Empty:   -> BTree;
  BTree_Create:  BTree * BTree * elem -> BTree;
  BTree_IsEmpty: BTree -> Boolean;
  BTree_Root:    BTree(t) -> elem
     pre: not BTree_IsEmpty(t);
  BTree_Left:    BTree(t) -> BTree
     pre: not BTree_IsEmpty(t);
  BTree_Right:   BTree(t) -> BTree
     pre: not BTree_IsEmpty(t);
  belongs:       elem * BTree -> Boolean;

AXIOMS t1, t2: BTree; e, e1: elem;

  BTree_IsEmpty(BTree_Empty())            = True;
  BTree_IsEmpty(BTree_Create(t1, t2, e))  = False;
  BTree_Root(BTree_Create(t1, t2, e))     = e;
  BTree_Left(BTree_Create(t1, t2, e))     = t1;
  BTree_Right(BTree_Create(t1, t2, e))    = t2;
  belongs(e, BTree_Empty())               = False;
  belongs(e, BTree_Create(t1, t2, e1))    =
      (e = e1) or (belongs(e, t1) or belongs(e, t2));

END-CLASS


-- ============================================================
-- ExprTree — el árbol de sintaxis propiamente dicho.
-- Subtipo de BTree[String]: agrega dos constructores propios
--   * leaf(x)        — una hoja con el operando x;
--   * node(s, l, r)  — un nodo operador s con hijos l y r;
-- definidos en términos de los constructores heredados, y
-- cuatro operaciones derivadas por recursión sobre ellos.
-- ============================================================

CLASS ExprTree
IMPORTS Integer, String
IS-SUBTYPE-OF BTree[String]
BASIC CONSTRUCTORS leaf, node
EFFECTIVE
OPERATIONS

  -- ─── Constructores ─────────────────────────────────────
  -- Una hoja: un árbol con dos subárboles vacíos cuya raíz
  -- es el operando.
  leaf: String -> ExprTree;

  -- Un nodo interno: la raíz es el símbolo del operador y los
  -- subárboles son las dos sub-expresiones. La precondición
  -- restringe el símbolo a los cinco operadores admitidos.
  node: String(s) * ExprTree * ExprTree -> ExprTree
     pre: (s = "+") or (s = "-") or (s = "*") or (s = "/")
          or (s = "**");

  -- ─── Observadores ──────────────────────────────────────
  -- ¿Es una hoja (un operando) o un nodo operador?
  isLeaf:       ExprTree -> Boolean;

  -- Cantidad de operandos (hojas) del árbol.
  numOperands:  ExprTree -> Integer;

  -- Cantidad de operadores (nodos internos) del árbol.
  numOperators: ExprTree -> Integer;

  -- Reconstruye la expresión aritmética totalmente
  -- parentizada que el árbol representa.
  render:       ExprTree -> String;

AXIOMS  l, r: ExprTree;  x, s: String;

  -- ──────────────────────────────────────────────────────
  -- Definición de los constructores en términos de BTree.
  -- ──────────────────────────────────────────────────────
  leaf(x) =
      BTree_Create(BTree_Empty() as ExprTree,
                   BTree_Empty() as ExprTree,
                   x) as ExprTree;

  node(s, l, r) = BTree_Create(l, r, s) as ExprTree;

  -- ──────────────────────────────────────────────────────
  -- isLeaf.
  -- ──────────────────────────────────────────────────────
  isLeaf(leaf(x))       = True;
  isLeaf(node(s, l, r)) = False;

  -- ──────────────────────────────────────────────────────
  -- numOperands: una hoja aporta 1; un nodo, la suma de sus
  -- hijos.
  -- ──────────────────────────────────────────────────────
  numOperands(leaf(x))       = 1;
  numOperands(node(s, l, r)) = numOperands(l) + numOperands(r);

  -- ──────────────────────────────────────────────────────
  -- numOperators: una hoja aporta 0; un nodo, 1 más la suma
  -- de sus hijos.
  -- ──────────────────────────────────────────────────────
  numOperators(leaf(x))       = 0;
  numOperators(node(s, l, r)) = 1 + numOperators(l) + numOperators(r);

  -- ──────────────────────────────────────────────────────
  -- render: reconstruye la expresión aritmética parentizada.
  --   * una hoja se imprime tal cual (su operando);
  --   * un nodo se imprime como "( izquierda operador derecha )".
  --
  -- ATENCIÓN a la doble lectura del símbolo `+` en el axioma
  -- del nodo. Conviven dos `+` que NO son lo mismo:
  --   * el `+` que une los trozos del resultado
  --       "(" + render(l) + s + render(r) + ")"
  --     es la CONCATENACIÓN de String. Todos sus argumentos
  --     son String, así que Nereus lo resuelve como el `+`
  --     del tipo String, no como suma aritmética.
  --   * el `+` del lenguaje de expresiones que el árbol MODELA
  --     no aparece aquí como operador: viaja como DATO. Es el
  --     valor String "+" guardado en un nodo, o sea la
  --     variable `s` cuando vale "+".
  -- Por eso, cuando s = "+", render simplemente CONCATENA ese
  -- carácter "+" como texto entre los dos lados; nunca suma
  -- nada. render imprime la expresión, no la evalúa: la
  -- aritmética (sumar, multiplicar...) no se calcula.
  --
  -- Sobre el ejemplo del encabezado, render produce la forma
  -- canónica  (((a+b)*c)/(c+d))  — totalmente parentizada;
  -- el par de paréntesis más externo es redundante a nivel
  -- raíz pero se incluye para que toda subexpresión tenga la
  -- misma forma.
  -- ──────────────────────────────────────────────────────
  render(leaf(x))       = x;
  render(node(s, l, r)) = "(" + render(l) + s + render(r) + ")";

END-CLASS
