Transformando expresión dada en notación de prefijo, identificando subexpresiones comunes y dependencias

Question

Me dan un montón de expresiones en notación de prefijo en un archivo de texto ANSI. Me gustaría producir otro archivo de texto ANSI que contenga la evaluación paso a paso de estas expresiones. Por ejemplo:

- +^x 2^y 2 1 

debe convertirse en

t1 = x^2 
t2 = y^2 
t3 = t1 + t2 
t4 = t3 - 1 
t4 is the result 

También tengo para identificar subexpresiones comunes. Por ejemplo dado

expression_1: z =^x 2 
expression_2: - + z^y 2 1 
expression_3: - z y 

Tengo que generar una salida diciendo que x aparece en las expresiones 1, 2 y 3 (a través de z).

tengo para identificar dependecies: expresión_1 sólo depende de x, expresión_2 depende de X e Y, etc.

El problema original es más difícil que los ejemplos anteriores y que no tienen control sobre el formato de entrada, se está en notación de prefijo de una manera mucho más complicada que las anteriores.

Ya tengo una implementación de trabajo en C++, sin embargo, es mucho dolor hacer tales cosas en C++.

¿Qué lenguaje de programación es el más adecuado para este tipo de problemas?

¿Podría recomendarme un tutorial/sitio web/libro donde podría comenzar?

¿Qué palabras clave debo buscar?

ACTUALIZACIÓN: Según las respuestas, los ejemplos anteriores son algo desafortunados, tengo operadores unarios, binarios y n-arios en la entrada. (Si se preguntan, exp es un operador unario, sum largo de un intervalo es un operador n-ario.)

Answer 1

El problema consiste en dos subproblemas: el análisis y la manipulación simbólica. Me parece que la respuesta se reduce a dos posibles soluciones.

Una de ellas es poner en práctica todo desde cero: "Yo te recomiendo crear el árbol de expresión completo si desea conservar la máxima flexibilidad para el manejo de casos difíciles." - propuesto por Rex. Como Sven señala: "cualquiera de los lenguajes de alto nivel que enlistas es casi igualmente adecuado para la tarea", sin embargo, "Python (o cualquiera de los idiomas de alto nivel que enumeró) no eliminará la complejidad del problema. "
Recibí muy buenas soluciones en Scala (muchas gracias por Rex y Daniel), un buen ejemplo en Python (de Sven). Sin embargo, todavía estoy interesado en las soluciones Lisp, Haskell o Erlang.

La otra solución es utilizar alguna biblioteca/software existente para la tarea, con todos los pros y los contras implícitas. Los candidatos son Maxima (Common Lisp), SymPy (Python, propuesto por payne) y GiNaC (C++).

Answer 2

El paquete pitón sympy hace álgebra simbólica, incluyendo la eliminación subexpresión común y generar pasos de evaluación para un conjunto de expresiones.

Ver: http://docs.sympy.org/dev/modules/rewriting.html (Mire el método cse en la parte inferior de la página).

Answer 3

para darle una idea de cómo se vería en Python, aquí es un código de ejemplo:

operators = "+-*/^" 

def parse(it, count=1): 
    token = next(it) 
    if token in operators: 
     op1, count = parse(it, count) 
     op2, count = parse(it, count) 
     tmp = "t%s" % count 
     print tmp, "=", op1, token, op2 
     return tmp, count + 1 
    return token, count 

s = "- +^x 2^y 2 1" 
a = s.split() 
res, dummy = parse(iter(a)) 
print res, "is the result" 

La salida es la misma que su salida de ejemplo.

Dejando a un lado este ejemplo, creo que cualquiera de los idiomas de alto nivel que enumeró son casi igualmente adecuados para la tarea.

Answer 4

El ejemplo de Python es elegantemente corto, pero sospecho que en realidad no tendrá suficiente control sobre sus expresiones de esa manera. Es mucho mejor que construyas un árbol de expresiones, aunque requiera más trabajo, y luego consultes el árbol. He aquí un ejemplo en Scala (apto para cortar y pegar en el REPL):

object OpParser { 
    private def estr(oe: Option[Expr]) = oe.map(_.toString).getOrElse("_") 
    case class Expr(text: String, left: Option[Expr] = None, right: Option[Expr] = None) { 
    import Expr._ 
    def varsUsed: Set[String] = text match { 
     case Variable(v) => Set(v) 
     case Op(o) => 
     left.map(_.varsUsed).getOrElse(Set()) ++ right.map(_.varsUsed).getOrElse(Set()) 
     case _ => Set() 
    } 
    def printTemp(n: Int = 0, depth: Int = 0): (String,Int) = text match { 
     case Op(o) => 
     val (tl,nl) = left.map(_.printTemp(n,depth+1)).getOrElse(("_",n)) 
     val (tr,nr) = right.map(_.printTemp(nl,depth+1)).getOrElse(("_",n)) 
     val t = "t"+(nr+1) 
     println(t + " = " + tl + " " + text + " " + tr) 
     if (depth==0) println(t + " is the result") 
     (t, nr+1) 
     case _ => (text, n) 
    } 
    override def toString: String = { 
     if (left.isDefined || right.isDefined) { 
     "(" + estr(left) + " " + text + " " + estr(right) + ")" 
     } 
     else text 
    } 
    } 
    object Expr { 
    val Digit = "([0-9]+)"r 
    val Variable = "([a-z])"r 
    val Op = """([+\-*/^])"""r 
    def parse(s: String) = { 
     val bits = s.split(" ") 
     val parsed = (
     if (bits.length > 2 && Variable.unapplySeq(bits(0)).isDefined && bits(1)=="=") { 
      parseParts(bits,2) 
     } 
     else parseParts(bits) 
    ) 
     parsed.flatMap(p => if (p._2<bits.length) None else Some(p._1)) 
    } 
    def parseParts(as: Array[String], from: Int = 0): Option[(Expr,Int)] = { 
     if (from >= as.length) None 
     else as(from) match { 
     case Digit(n) => Some(Expr(n), from+1) 
     case Variable(v) => Some(Expr(v), from+1) 
     case Op(o) => 
      parseParts(as, from+1).flatMap(lhs => 
      parseParts(as, lhs._2).map(rhs => (Expr(o,Some(lhs._1),Some(rhs._1)), rhs._2)) 
     ) 
     case _ => None 
     } 
    } 
    } 
} 

Esto puede ser un poco mucho para digerir todos a la vez, pero de nuevo, esta vez hace mucho.

En primer lugar, es completamente a prueba de balas (tenga en cuenta el uso intensivo de Option donde un resultado puede fallar). Si arrojas basura, simplemente devolverá None. (Con un poco más de trabajo, puede hacer que se queje sobre el problema de manera informativa; básicamente, el case Op(o) que luego contiene parseParts anidado dos veces podría almacenar los resultados e imprimir un mensaje de error informativo si el operador no recibió dos argumentos. Del mismo modo, parse podría quejarse de los valores finales en lugar de simplemente devolver None.)

En segundo lugar, cuando haya terminado con él, tendrá un árbol de expresiones completo. Tenga en cuenta que printTemp imprime las variables temporales que desea, y varsUsed enumera las variables utilizadas en una expresión particular, que puede usar para expandir a una lista completa una vez que analiza múltiples líneas. (Es posible que necesite jugar un poco con la expresión regular si las variables pueden ser más que a a z). Tenga en cuenta también que el árbol de expresiones se imprime a sí mismo en notación infija normal. Veamos algunos ejemplos:

scala> OpParser.Expr.parse("4") 
res0: Option[OpParser.Expr] = Some(4) 

scala> OpParser.Expr.parse("+ + + + + 1 2 3 4 5 6") 
res1: Option[OpParser.Expr] = Some((((((1 + 2) + 3) + 4) + 5) + 6)) 

scala> OpParser.Expr.parse("- +^x 2^y 2 1") 
res2: Option[OpParser.Expr] = Some((((x^2) + (y^2)) - 1)) 

scala> OpParser.Expr.parse("+ + 4 4 4 4") // Too many 4s! 
res3: Option[OpParser.Expr] = None 

scala> OpParser.Expr.parse("Q#$S!M$#!*)000") // Garbage! 
res4: Option[OpParser.Expr] = None 

scala> OpParser.Expr.parse("z =") // Assigned nothing?! 
res5: Option[OpParser.Expr] = None 

scala> res2.foreach(_.printTemp()) 
t1 = x^2 
t2 = y^2 
t3 = t1 + t2 
t4 = t3 - 1 
t4 is the result 

scala> res2.map(_.varsUsed)  
res10: Option[Set[String]] = Some(Set(x, y)) 

Ahora, usted podría hacer esto en Python también sin demasiado trabajo adicional, y en un número de los otros idiomas además. Prefiero usar Scala, pero es posible que prefiera lo contrario. A pesar de todo, recomiendo crear el árbol de expresiones completo si desea mantener la máxima flexibilidad para manejar casos complicados.

Answer 5

La notación de prefijo es realmente simple de hacer con los analizadores sintácticos recursivos. Por ejemplo:

object Parser { 
    val Subexprs = collection.mutable.Map[String, String]() 
    val Dependencies = collection.mutable.Map[String, Set[String]]().withDefaultValue(Set.empty) 
    val TwoArgsOp = "([-+*/^])".r  // - at the beginning,^at the end 
    val Ident = "(\\p{Alpha}\\w*)".r 
    val Literal = "(\\d+)".r 

    var counter = 1 
    def getIdent = { 
     val ident = "t" + counter 
     counter += 1 
     ident 
    } 

    def makeOp(op: String) = { 
     val op1 = expr 
     val op2 = expr 
     val ident = getIdent 
     val subexpr = op1 + " " + op + " " + op2 
     Subexprs(ident) = subexpr 
     Dependencies(ident) = Dependencies(op1) ++ Dependencies(op2) + op1 + op2 
     ident 
    } 

    def expr: String = nextToken match { 
     case TwoArgsOp(op) => makeOp(op) 
     case Ident(id)  => id 
     case Literal(lit) => lit 
     case x    => error("Unknown token "+x) 
    } 

    def nextToken = tokens.next 
    var tokens: Iterator[String] = _ 

    def parse(input: String) = { 
     tokens = input.trim split "\\s+" toIterator; 
     counter = 1 
     expr 
     if (tokens.hasNext) 
      error("Input not fully parsed: "+tokens.mkString(" ")) 

     (Subexprs, Dependencies) 
    } 
} 

Esto generará una salida como ésta:

scala> val (subexpressions, dependencies) = Parser.parse("- +^x 2^y 2 1") 
subexpressions: scala.collection.mutable.Map[String,String] = Map(t3 -> t1 + t2, t4 -> t3 - 1, t1 -> x^2, t2 -> y^2) 
dependencies: scala.collection.mutable.Map[String,Set[String]] = Map(t3 -> Set(x, y, t2, 2, t1), t4 -> Set(x, y, t3, t2, 1, 2, t1), t1 -> Set(x, 2), t 
2 -> Set(y, 2)) 

scala> subexpressions.toSeq.sorted foreach println 
(t1,x^2) 
(t2,y^2) 
(t3,t1 + t2) 
(t4,t3 - 1) 

scala> dependencies.toSeq.sortBy(_._1) foreach println 
(t1,Set(x, 2)) 
(t2,Set(y, 2)) 
(t3,Set(x, y, t2, 2, t1)) 
(t4,Set(x, y, t3, t2, 1, 2, t1)) 

esto se puede ampliar fácilmente. Por ejemplo, para manejar múltiples cuentas de expresión que puede utilizar esto:

object Parser { 
    val Subexprs = collection.mutable.Map[String, String]() 
    val Dependencies = collection.mutable.Map[String, Set[String]]().withDefaultValue(Set.empty) 
    val TwoArgsOp = "([-+*/^])".r  // - at the beginning,^at the end 
    val Ident = "(\\p{Alpha}\\w*)".r 
    val Literal = "(\\d+)".r 

    var counter = 1 
    def getIdent = { 
     val ident = "t" + counter 
     counter += 1 
     ident 
    } 

    def makeOp(op: String) = { 
     val op1 = expr 
     val op2 = expr 
     val ident = getIdent 
     val subexpr = op1 + " " + op + " " + op2 
     Subexprs(ident) = subexpr 
     Dependencies(ident) = Dependencies(op1) ++ Dependencies(op2) + op1 + op2 
     ident 
    } 

    def expr: String = nextToken match { 
     case TwoArgsOp(op) => makeOp(op) 
     case Ident(id)  => id 
     case Literal(lit) => lit 
     case x    => error("Unknown token "+x) 
    } 

    def assignment: Unit = { 
     val ident = nextToken 
     nextToken match { 
      case "=" => 
       val tmpIdent = expr 
       Dependencies(ident) = Dependencies(tmpIdent) 
       Subexprs(ident) = Subexprs(tmpIdent) 
       Dependencies.remove(tmpIdent) 
       Subexprs.remove(tmpIdent) 
      case x => error("Expected assignment, got "+x) 
     } 
    } 

    def stmts: Unit = while(tokens.hasNext) tokens.head match { 
     case TwoArgsOp(_) => expr 
     case Ident(_)  => assignment 
     case x   => error("Unknown statement starting with "+x) 
    } 

    def nextToken = tokens.next 
    var tokens: BufferedIterator[String] = _ 

    def parse(input: String) = { 
     tokens = (input.trim split "\\s+" toIterator).buffered 
     counter = 1 
     stmts 
     if (tokens.hasNext) 
      error("Input not fully parsed: "+tokens.mkString(" ")) 

     (Subexprs, Dependencies) 
    } 
} 

Rendimiento:

scala> val (subexpressions, dependencies) = Parser.parse(""" 
    | z =^x 2 
    | - + z^y 2 1 
    | - z y 
    | """) 
subexpressions: scala.collection.mutable.Map[String,String] = Map(t3 -> z + t2, t5 -> z - y, t4 -> t3 - 1, z -> x^2, t2 -> y^2) 
dependencies: scala.collection.mutable.Map[String,Set[String]] = Map(t3 -> Set(x, y, t2, 2, z), t5 -> Set(x, 2, z, y), t4 -> Set(x, y, t3, t2, 1, 2, z 
), z -> Set(x, 2), t2 -> Set(y, 2)) 

scala> subexpressions.toSeq.sorted foreach println 
(t2,y^2) 
(t3,z + t2) 
(t4,t3 - 1) 
(t5,z - y) 
(z,x^2) 

scala> dependencies.toSeq.sortBy(_._1) foreach println 
(t2,Set(y, 2)) 
(t3,Set(x, y, t2, 2, z)) 
(t4,Set(x, y, t3, t2, 1, 2, z)) 
(t5,Set(x, 2, z, y)) 
(z,Set(x, 2)) 

Answer 6

Ok, ya que los analizadores recursivos no son lo tuyo, aquí es una alternativa con combinadores de análisis sintáctico:

object PrefixParser extends JavaTokenParsers { 
    import scala.collection.mutable 

    // Maps generated through parsing 

    val Subexprs = mutable.Map[String, String]() 
    val Dependencies = mutable.Map[String, Set[String]]().withDefaultValue(Set.empty) 

    // Initialize, read, parse & evaluate string 

    def read(input: String) = { 
     counter = 1 
     Subexprs.clear 
     Dependencies.clear 
     parseAll(stmts, input) 
    } 

    // Grammar 

    def stmts    = stmt+ 
    def stmt    = assignment | expr 
    def assignment   = (ident <~ "=") ~ expr ^^ assignOp 
    def expr: P    = subexpr | identifier | number 
    def subexpr: P   = twoArgs | nArgs 
    def twoArgs: P   = operator ~ expr ~ expr ^^ twoArgsOp 
    def nArgs: P   = "sum" ~ ("\\d+".r >> args) ^^ nArgsOp 
    def args(n: String): Ps = repN(n.toInt, expr) 
    def operator   = "[-+*/^]".r 
    def identifier   = ident ^^ (id => Result(id, Set(id))) 
    def number    = wholeNumber ^^ (Result(_, Set.empty)) 

    // Evaluation helper class and types 

    case class Result(ident: String, dependencies: Set[String]) 
    type P = Parser[Result] 
    type Ps = Parser[List[Result]] 

    // Evaluation methods 

    def assignOp: (String ~ Result) => Result = { 
     case ident ~ result => 
      val value = assign(ident, 
           Subexprs(result.ident), 
           result.dependencies - result.ident) 
      Subexprs.remove(result.ident) 
      Dependencies.remove(result.ident) 
      value 
    } 

    def assign(ident: String, 
       value: String, 
       dependencies: Set[String]): Result = { 
     Subexprs(ident) = value 
     Dependencies(ident) = dependencies 
     Result(ident, dependencies) 
    } 

    def twoArgsOp: (String ~ Result ~ Result) => Result = { 
     case op ~ op1 ~ op2 => makeOp(op, op1, op2) 
    } 

    def makeOp(op: String, 
       op1: Result, 
       op2: Result): Result = { 
     val ident = getIdent 
     assign(ident, 
       "%s %s %s" format (op1.ident, op, op2.ident), 
       op1.dependencies ++ op2.dependencies + ident) 
    } 

    def nArgsOp: (String ~ List[Result]) => Result = { 
     case op ~ ops => makeNOp(op, ops) 
    } 

    def makeNOp(op: String, ops: List[Result]): Result = { 
     val ident = getIdent 
     assign(ident, 
       "%s(%s)" format (op, ops map (_.ident) mkString ", "), 
       ops.foldLeft(Set(ident))(_ ++ _.dependencies)) 
    } 

    var counter = 1 
    def getIdent = { 
     val ident = "t" + counter 
     counter += 1 
     ident 
    } 

    // Debugging helper methods 

    def printAssignments = Subexprs.toSeq.sorted foreach println 
    def printDependencies = Dependencies.toSeq.sortBy(_._1) map { 
     case (id, dependencies) => (id, dependencies - id) 
    } foreach println 

} 

Este es el tipo de resultados que obtienes:

scala> PrefixParser.read(""" 
    | z =^x 2 
    | - + z^y 2 1 
    | - z y 
    | """) 
res77: PrefixParser.ParseResult[List[PrefixParser.Result]] = [5.1] parsed: List(Result(z,Set(x)), Result(t4,Set(t4, y, t3, t2, z)), Result(t5,Set(z, y 
, t5))) 

scala> PrefixParser.printAssignments 
(t2,y^2) 
(t3,z + t2) 
(t4,t3 - 1) 
(t5,z - y) 
(z,x^2) 

scala> PrefixParser.printDependencies 
(t2,Set(y)) 
(t3,Set(z, y, t2)) 
(t4,Set(y, t3, t2, z)) 
(t5,Set(z, y)) 
(z,Set(x)) 

operador n-ario

scala> PrefixParser.read(""" 
    | x = sum 3 + 1 2 * 3 4 5 
    | * x x 
    | """) 
res93: PrefixParser.ParseResult[List[PrefixParser.Result]] = [4.1] parsed: List(Result(x,Set(t1, t2)), Result(t4,Set(x, t4))) 

scala> PrefixParser.printAssignments 
(t1,1 + 2) 
(t2,3 * 4) 
(t4,x * x) 
(x,sum(t1, t2, 5)) 

scala> PrefixParser.printDependencies 
(t1,Set()) 
(t2,Set()) 
(t4,Set(x)) 
(x,Set(t1, t2)) 

Answer 7

Resulta que este tipo de análisis es de interés para mí también, por lo que he hecho un poco más de trabajo en ella.

Parece haber un sentimiento de que cosas como la simplificación de expresiones es difícil. No estoy muy seguro. Echemos un vistazo a una solución bastante completa. (La impresión de expresiones tn no es útil para mí, y ya tiene varios ejemplos de Scala, así que lo omitiré)

Primero, necesitamos extraer las diversas partes del idioma.Seleccionaré expresiones regulares, aunque también se pueden usar los combinadores de analizadores:

object OpParser { 
    val Natural = "([0-9]+)"r 
    val Number = """((?:-)?[0-9]+(?:\.[0-9]+)?(?:[eE](?:-)?[0-9]+)?)"""r 
    val Variable = "([a-z])"r 
    val Unary = "(exp|sin|cos|tan|sqrt)"r 
    val Binary = "([-+*/^])"r 
    val Nary = "(sum|prod|list)"r 

Bastante sencillo. Definimos las diversas cosas que pueden aparecer. (He decidido que las variables definidas por el usuario solo pueden ser una sola letra minúscula, y que los números pueden ser de coma flotante ya que tiene la función exp). El r al final significa que esta es una expresión regular, y dará nosotros las cosas entre paréntesis.

Ahora tenemos que representar nuestro árbol. Hay varias maneras de hacerlo, pero elegiré una clase base abstracta con expresiones específicas como clases de casos, ya que esto hace que la coincidencia de patrones sea fácil. Además, es posible que deseemos una buena impresión, por lo que anularemos toString. En su mayoría, sin embargo, usaremos funciones recursivas para hacer el trabajo pesado.

abstract class Expr { 
    def text: String 
    def args: List[Expr] 
    override def toString = args match { 
     case l :: r :: Nil => "(" + l + " " + text + " " + r + ")" 
     case Nil => text 
     case _ => args.mkString(text+"(", ",", ")") 
    } 
    } 
    case class Num(text: String, args: List[Expr]) extends Expr { 
    val quantity = text.toDouble 
    } 
    case class Var(text: String, args: List[Expr]) extends Expr { 
    override def toString = args match { 
     case arg :: Nil => "(" + text + " <- " + arg + ")" 
     case _ => text 
    } 
    } 
    case class Una(text: String, args: List[Expr]) extends Expr 
    case class Bin(text: String, args: List[Expr]) extends Expr 
    case class Nar(text: String, args: List[Expr]) extends Expr { 
    override def toString = text match { 
     case "list" => 
     (for ((a,i) <- args.zipWithIndex) yield { 
      "%3d: %s".format(i+1,a.toString) 
     }).mkString("List[\n","\n","\n]") 
     case _ => super.toString 
    } 
    } 

Sobre todo esto es bastante aburrido - cada clase caso anula la clase base, y el text y args rellenar automáticamente para el def. Tenga en cuenta que he decidido que un list es una función n-aria posible, y que se imprimirá con números de línea. (La razón es que si tiene varias líneas de entrada, a veces es más conveniente trabajar con todas juntas como una expresión; esto les permite ser una función).

Una vez definidas nuestras estructuras de datos, debemos analizar las expresiones. Es conveniente representar las cosas para analizar como una lista de tokens; como analizamos, devolveremos tanto una expresión como los tokens restantes que no hemos analizado; esta es una estructura particularmente útil para el análisis recursivo. Por supuesto, es posible que no analicemos nada, por lo que es mejor incluirlo también en Option.

def parse(tokens: List[String]): Option[(Expr,List[String])] = tokens match { 
    case Variable(x) :: "=" :: rest => 
     for ((expr,remains) <- parse(rest)) yield (Var(x,List(expr)), remains) 
    case Variable(x) :: rest => Some(Var(x,Nil), rest) 
    case Number(n) :: rest => Some(Num(n,Nil), rest) 
    case Unary(u) :: rest => 
     for ((expr,remains) <- parse(rest)) yield (Una(u,List(expr)), remains) 
    case Binary(b) :: rest => 
     for ((lexp,lrem) <- parse(rest); (rexp,rrem) <- parse(lrem)) yield 
     (Bin(b,List(lexp,rexp)), rrem) 
    case Nary(a) :: Natural(b) :: rest => 
     val buffer = new collection.mutable.ArrayBuffer[Expr] 
     def parseN(tok: List[String], n: Int = b.toInt): List[String] = { 
     if (n <= 0) tok 
     else { 
      for ((expr,remains) <- parse(tok)) yield { buffer += expr; parseN(remains, n-1) } 
     }.getOrElse(tok) 
     } 
     val remains = parseN(rest) 
     if (buffer.length == b.toInt) Some(Nar(a,buffer.toList), remains) 
     else None 
    case _ => None 
    } 

en cuenta que utilizamos coincidencia de patrones y la recursividad para hacer la mayor parte del trabajo pesado - que escoger de parte de la lista, calcular la cantidad de argumentos que necesitamos, y pasar a lo largo de los recursiva. La operación N-ary es un poco menos amigable, pero creamos una pequeña función recursiva que analizará N cosas a la vez para nosotros, almacenando los resultados en un buffer.

Por supuesto, esto es un poco desagradable de usar, por lo que añadir algunas funciones de contenedor que nos permiten interconectar con ella muy bien:

def parse(s: String): Option[Expr] = parse(s.split(" ").toList).flatMap(x => { 
    if (x._2.isEmpty) Some(x._1) else None 
    }) 
    def parseLines(ls: List[String]): Option[Expr] = { 
    val attempt = ls.map(parse).flatten 
    if (attempt.length<ls.length) None 
    else if (attempt.length==1) attempt.headOption 
    else Some(Nar("list",attempt)) 
    } 

Bien, ahora, ¿qué pasa con la simplificación? Una cosa que podríamos querer hacer es simplificación numérica, donde precomputamos las expresiones y reemplazamos la expresión original con la versión reducida de la misma. Eso suena como una especie de operación recursiva: encontrar números y combinarlos. En primer lugar tenemos algunas funciones de ayuda a hacer cálculos en números:

def calc(n: Num, f: Double => Double): Num = Num(f(n.quantity).toString, Nil) 
    def calc(n: Num, m: Num, f: (Double,Double) => Double): Num = 
    Num(f(n.quantity,m.quantity).toString, Nil) 
    def calc(ln: List[Num], f: (Double,Double) => Double): Num = 
    Num(ln.map(_.quantity).reduceLeft(f).toString, Nil) 

y luego hacemos la simplificación:

def numericSimplify(expr: Expr): Expr = expr match { 
    case Una(t,List(e)) => numericSimplify(e) match { 
     case n @ Num(_,_) => t match { 
     case "exp" => calc(n, math.exp _) 
     case "sin" => calc(n, math.sin _) 
     case "cos" => calc(n, math.cos _) 
     case "tan" => calc(n, math.tan _) 
     case "sqrt" => calc(n, math.sqrt _) 
     } 
     case a => Una(t,List(a)) 
    } 
    case Bin(t,List(l,r)) => (numericSimplify(l), numericSimplify(r)) match { 
     case (n @ Num(_,_), m @ Num(_,_)) => t match { 
     case "+" => calc(n, m, _ + _) 
     case "-" => calc(n, m, _ - _) 
     case "*" => calc(n, m, _ * _) 
     case "/" => calc(n, m, _/_) 
     case "^" => calc(n, m, math.pow) 
     } 
     case (a,b) => Bin(t,List(a,b)) 
    } 
    case Nar("list",list) => Nar("list",list.map(numericSimplify)) 
    case Nar(t,list) => 
     val simple = list.map(numericSimplify) 
     val nums = simple.collect { case n @ Num(_,_) => n } 
     if (simple.length == 0) t match { 
     case "sum" => Num("0",Nil) 
     case "prod" => Num("1",Nil) 
     } 
     else if (nums.length == simple.length) t match { 
     case "sum" => calc(nums, _ + _) 
     case "prod" => calc(nums, _ * _) 
     } 
     else Nar(t, simple) 
    case Var(t,List(e)) => Var(t, List(numericSimplify(e))) 
    case _ => expr 
    } 

Aviso de nuevo el uso intensivo de coincidencia de patrones para encontrar cuando estamos en un buen caso, y para enviar el cálculo apropiado.

¡Ahora, seguramente la sustitución algebraica es mucho más difícil! En realidad, todo lo que necesita hacer es observar que ya se ha utilizado una expresión y asignar una variable. Como la sintaxis que he definido arriba permite la sustitución de variables in situ, podemos simplemente modificar nuestro árbol de expresiones para incluir más asignaciones de variables.Por lo que hacemos (editado para insertar variables solamente si el usuario no tiene):

def algebraicSimplify(expr: Expr): Expr = { 
    val all, dup, used = new collection.mutable.HashSet[Expr] 
    val made = new collection.mutable.HashMap[Expr,Int] 
    val user = new collection.mutable.HashMap[Expr,Expr] 
    def findExpr(e: Expr) { 
     e match { 
     case Var(t,List(v)) => 
      user += v -> e 
      if (all contains e) dup += e else all += e 
     case Var(_,_) | Num(_,_) => // Do nothing in these cases 
     case _ => if (all contains e) dup += e else all += e 
     } 
     e.args.foreach(findExpr) 
    } 
    findExpr(expr) 
    def replaceDup(e: Expr): Expr = { 
     if (made contains e) Var("x"+made(e),Nil) 
     else if (used contains e) Var(user(e).text,Nil) 
     else if (dup contains e) { 
     val fixed = replaceDupChildren(e) 
     made += e -> made.size 
     Var("x"+made(e),List(fixed)) 
     } 
     else replaceDupChildren(e) 
    } 
    def replaceDupChildren(e: Expr): Expr = e match { 
     case Una(t,List(u)) => Una(t,List(replaceDup(u))) 
     case Bin(t,List(l,r)) => Bin(t,List(replaceDup(l),replaceDup(r))) 
     case Nar(t,list) => Nar(t,list.map(replaceDup)) 
     case Var(t,List(v)) => 
     used += v 
     Var(t,List(if (made contains v) replaceDup(v) else replaceDupChildren(v))) 
     case _ => e 
    } 
    replaceDup(expr) 
    } 

Eso es todo - una rutina de sustitución algebraica completamente funcional. Tenga en cuenta que crea conjuntos de expresiones que se ven, manteniendo una pista especial de cuáles son duplicados. Gracias a la magia de las clases de casos, todas las equidades están definidas para nosotros, por lo que solo funciona. Luego podemos reemplazar cualquier duplicado a medida que recurrimos para encontrarlos. Tenga en cuenta que la rutina replace se divide por la mitad, y que coincide con en una versión no reemplazada del árbol, pero utiliza una versión reemplazada.

Bien, ahora vamos a añadir algunas pruebas:

def main(args: Array[String]) { 
    val test1 = "- +^x 2^y 2 1" 
    val test2 = "+ + +" // Bad! 
    val test3 = "exp sin cos sum 5" // Bad! 
    val test4 = "+ * 2 3^3 2" 
    val test5 = List(test1, test4, "^ y 2").mkString("list 3 "," ","") 
    val test6 = "+ + x y + + * + x y + 4 5 * + x y + 4 y + + x y + 4 y" 

    def performTest(test: String) = { 
     println("Start with: " + test) 
     val p = OpParser.parse(test) 
     if (p.isEmpty) println(" Parsing failed") 
     else { 
     println("Parsed:  " + p.get) 
     val q = OpParser.numericSimplify(p.get) 
     println("Numeric: " + q) 
     val r = OpParser.algebraicSimplify(q) 
     println("Algebraic: " + r) 
     } 
     println 
    } 

    List(test1,test2,test3,test4,test5,test6).foreach(performTest) 
    } 
} 

¿Cómo lo hace?

$ scalac OpParser.scala; scala OpParser 
Start with: - +^x 2^y 2 1 
Parsed:  (((x^2) + (y^2)) - 1) 
Numeric: (((x^2) + (y^2)) - 1) 
Algebraic: (((x^2) + (y^2)) - 1) 

Start with: + + + 
    Parsing failed 

Start with: exp sin cos sum 5 
    Parsing failed 

Start with: + * 2 3^3 2 
Parsed:  ((2 * 3) + (3^2)) 
Numeric: 15.0 
Algebraic: 15.0 

Start with: list 3 - +^x 2^y 2 1 + * 2 3^3 2^y 2 
Parsed:  List[ 
    1: (((x^2) + (y^2)) - 1) 
    2: ((2 * 3) + (3^2)) 
    3: (y^2) 
] 
Numeric: List[ 
    1: (((x^2) + (y^2)) - 1) 
    2: 15.0 
    3: (y^2) 
] 
Algebraic: List[ 
    1: (((x^2) + (x0 <- (y^2))) - 1) 
    2: 15.0 
    3: x0 
] 

Start with: + + x y + + * + x y + 4 5 * + x y + 4 y + + x y + 4 y 
Parsed:  ((x + y) + ((((x + y) * (4 + 5)) + ((x + y) * (4 + y))) + ((x + y) + (4 + y)))) 
Numeric: ((x + y) + ((((x + y) * 9.0) + ((x + y) * (4 + y))) + ((x + y) + (4 + y)))) 
Algebraic: ((x0 <- (x + y)) + (((x0 * 9.0) + (x0 * (x1 <- (4 + y)))) + (x0 + x1))) 

Así que no sé si eso es útil para usted, pero resulta ser útil para mí. Y este es el tipo de cosas que dudaría en abordar en C++ porque varias cosas que se suponía que serían fáciles terminaron siendo dolorosas.

---

Edición: He aquí un ejemplo del uso de esta estructura para imprimir asignaciones temporales, sólo para demostrar que esta estructura está perfectamente bien para hacer tales cosas.

Código:

def useTempVars(expr: Expr): Expr = { 
    var n = 0 
    def temp = { n += 1; "t"+n } 
    def replaceTemp(e: Expr, exempt: Boolean = false): Expr = { 
     def varify(x: Expr) = if (exempt) x else Var(temp,List(x)) 
     e match { 
     case Var(t,List(e)) => Var(t,List(replaceTemp(e, exempt = true))) 
     case Una(t,List(u)) => varify(Una(t, List(replaceTemp(u,false)))) 
     case Bin(t,lr) => varify(Bin(t, lr.map(replaceTemp(_,false)))) 
     case Nar(t,ls) => varify(Nar(t, ls.map(replaceTemp(_,false)))) 
     case _ => e 
     } 
    } 
    replaceTemp(expr) 
    } 
    def varCut(expr: Expr): Expr = expr match { 
    case Var(t,_) => Var(t,Nil) 
    case Una(t,List(u)) => Una(t,List(varCut(u))) 
    case Bin(t,lr) => Bin(t, lr.map(varCut)) 
    case Nar(t,ls) => Nar(t, ls.map(varCut)) 
    case _ => expr 
    } 
    def getAssignments(expr: Expr): List[Expr] = { 
    val children = expr.args.flatMap(getAssignments) 
    expr match { 
     case Var(t,List(e)) => children :+ expr 
     case _ => children 
    } 
    } 
    def listAssignments(expr: Expr): List[String] = { 
    getAssignments(expr).collect(e => e match { 
     case Var(t,List(v)) => t + " = " + varCut(v) 
    }) :+ (expr.text + " is the answer") 
    } 

resultados seleccionados (desde listAssignments(useTempVars(r)).foreach(printf(" %s\n",_))):

Start with: - +^x 2^y 2 1 
Assignments: 
    t1 = (x^2) 
    t2 = (y^2) 
    t3 = (t1 + t2) 
    t4 = (t3 - 1) 
    t4 is the answer 

Start with: + + x y + + * + x y + 4 5 * + x y + 4 y + + x y + 4 y 
Algebraic: ((x0 <- (x + y)) + (((x0 * 9.0) + (x0 * (x1 <- (4 + y)))) + (x0 + x1))) 
Assignments: 
    x0 = (x + y) 
    t1 = (x0 * 9.0) 
    x1 = (4 + y) 
    t2 = (x0 * x1) 
    t3 = (t1 + t2) 
    t4 = (x0 + x1) 
    t5 = (t3 + t4) 
    t6 = (x0 + t5) 
    t6 is the answer 

---

Segunda edición: encontrar dependencias tampoco es tan malo.

Código:

def directDepends(expr: Expr): Set[Expr] = expr match { 
    case Var(t,_) => Set(expr) 
    case _ => expr.args.flatMap(directDepends).toSet 
    } 
    def indirectDepends(expr: Expr) = { 
    val depend = getAssignments(expr).map(e => 
     e -> e.args.flatMap(directDepends).toSet 
    ).toMap 
    val tagged = for ((k,v) <- depend) yield (k.text -> v.map(_.text)) 
    def percolate(tags: Map[String,Set[String]]): Option[Map[String,Set[String]]] = { 
     val expand = for ((k,v) <- tags) yield (
     k -> (v union v.flatMap(x => tags.get(x).getOrElse(Set()))) 
    ) 
     if (tags.exists(kv => expand(kv._1) contains kv._1)) None // Cyclic dependency! 
     else if (tags == expand) Some(tags) 
     else percolate(expand) 
    } 
    percolate(tagged) 
    } 
    def listDependents(expr: Expr): List[(String,String)] = { 
    def sayNothing(s: String) = if (s=="") "nothing" else s 
    val e = expr match { 
     case Var(_,_) => expr 
     case _ => Var("result",List(expr)) 
    } 
    indirectDepends(e).map(_.toList.map(x => 
     (x._1, sayNothing(x._2.toList.sorted.mkString(" "))) 
    )).getOrElse(List((e.text,"cyclic"))) 
    } 

Y si añadimos nuevos casos de prueba val test7 = "list 3 z =^x 2 - + z^y 2 1 w = - z y" y val test8 = "list 2 x = y y = x" y mostramos las respuestas con for ((v,d) <- listDependents(r)) println(" "+v+" requires "+d) obtenemos (resultados seleccionados):

Start with: - +^x 2^y 2 1 
Dependencies: 
    result requires x y 

Start with: list 3 z =^x 2 - + z^y 2 1 w = - z y 
Parsed:  List[ 
    1: (z <- (x^2)) 
    2: ((z + (y^2)) - 1) 
    3: (w <- (z - y)) 
] 
Dependencies: 
    z requires x 
    w requires x y z 
    result requires w x y z 

Start with: list 2 x = y y = x 
Parsed:  List[ 
    1: (x <- y) 
    2: (y <- x) 
] 
Dependencies: 
    result requires cyclic 

Start with: + + x y + + * + x y + 4 5 * + x y + 4 y + + x y + 4 y 
Algebraic: ((x0 <- (x + y)) + (((x0 * 9.0) + (x0 * (x1 <- (4 + y)))) + (x0 + x1))) 
Dependencies: 
    x0 requires x y 
    x1 requires y 
    result requires x x0 x1 y 

así que creo que en la parte superior de este tipo de estructura, todos sus requisitos individuales se cumplen con bloques de una o dos docenas de líneas de código Scala.

---

Editar: aquí está la evaluación de expresiones, si se le ofrece un mapeo de Vars a valores:

def numericEvaluate(expr: Expr, initialValues: Map[String,Double]) = { 
    val chain = new collection.mutable.ArrayBuffer[(String,Double)] 
    val evaluated = new collection.mutable.HashMap[String,Double] 
    def note(xv: (String,Double)) { chain += xv; evaluated += xv } 
    evaluated ++= initialValues 
    def substitute(expr: Expr): Expr = expr match { 
     case Var(t,List(n @ Num(v,_))) => { note(t -> v.toDouble); n } 
     case Var(t,_) if (evaluated contains t) => Num(evaluated(t).toString,Nil) 
     case Var(t,ls) => Var(t,ls.map(substitute)) 
     case Una(t,List(u)) => Una(t,List(substitute(u))) 
     case Bin(t,ls) => Bin(t,ls.map(substitute)) 
     case Nar(t,ls) => Nar(t,ls.map(substitute)) 
     case _ => expr 
    } 
    def recurse(e: Expr): Expr = { 
     val sub = numericSimplify(substitute(e)) 
     if (sub == e) e else recurse(sub) 
    } 
    (recurse(expr), chain.toList) 
    } 

y se utiliza como tal en la rutina de la prueba:

 val (num,ops) = numericEvaluate(r,Map("x"->3,"y"->1.5)) 
     println("Evaluated:") 
     for ((v,n) <- ops) println(" "+v+" = "+n) 
     println(" result = " + num) 

dando resultados como estos (con entrada de x = 3 y y = 1.5):

Start with: list 3 - +^x 2^y 2 1 + * 2 3^3 2^y 2 
Algebraic: List[ 
    1: (((x^2) + (x0 <- (y^2))) - 1) 
    2: 15.0 
    3: x0 
] 
Evaluated: 
    x0 = 2.25 
    result = List[ 
    1: 10.25 
    2: 15.0 
    3: 2.25 
] 

Start with: list 3 z =^x 2 - + z^y 2 1 w = - z y 
Algebraic: List[ 
    1: (z <- (x^2)) 
    2: ((z + (y^2)) - 1) 
    3: (w <- (z - y)) 
] 
Evaluated: 
    z = 9.0 
    w = 7.5 
    result = List[ 
    1: 9.0 
    2: 10.25 
    3: 7.5 
] 

El otro desafío - escogiendo los VARs que aún no han sido utilizados - substracción apenas se fija fuera de las dependencias result lista. diff es el nombre del método de resta establecido.