package kapitel_05

/**
 * Beispiel aus
 *
 * - Algorithmen und Datenstrukturen für Dummies
 *   - von Andreas Gogol-Döring und Thomas Letschert
 *   - Verlag Wiley-VCH; Oktober 2019
 *  - Kapitel 5, Bäume: Immer einer über den anderen
 *
 * @author A. Gogol-Döring, Th. Letschert
 */

object AuD_05_12_ExpressionEvaluationWithStack_App extends App {

  sealed abstract class Exp
  case class Value(v: Int) extends Exp
  case class Add(e1: Exp, e2: Exp) extends Exp
  case class Sub(e1: Exp, e2: Exp) extends Exp
  case class Mult(e1: Exp, e2: Exp) extends Exp

  def eval(exp: Exp): Int = exp match {
    case Value(v) => v
    case Add(e1, e2) => eval(e1) + eval(e2)
    case Sub(e1, e2) => eval(e1) - eval(e2)
    case Mult(e1, e2) => eval(e1) * eval(e2)
  }


  sealed abstract class Node
  case class  ValueNode(v: Int) extends Node
  case object AddNode        extends Node
  case object SubNode        extends Node
  case object MultNode       extends Node

  def evalToNodes(exp: Exp): List[Node] = exp match {
    case Value(v) => List(ValueNode(v))
    case Add(e1, e2) => evalToNodes(e1) ++ evalToNodes(e2) ++ List(AddNode)
    case Sub(e1, e2) => evalToNodes(e1) ++ evalToNodes(e2) ++ List(SubNode)
    case Mult(e1, e2) => evalToNodes(e1) ++ evalToNodes(e2) ++ List(MultNode)
  }

  def evalNodes(nodes: List[Node], stack: List[Int]): Int = {
    nodes match {
      case Nil => stack.head
      case ValueNode(v) :: rest =>
        evalNodes(rest, v :: stack)
      case AddNode :: rest =>
        stack match {
          case x :: y :: stackRest => evalNodes(rest, y+x :: stackRest)
        }
      case SubNode :: rest =>
        stack match {
          case x :: y :: stackRest => evalNodes(rest, y-x :: stackRest)
        }
      case MultNode :: rest =>
        stack match {
          case x :: y :: stackRest => evalNodes(rest, y*x :: stackRest)
        }
    }
  }

  def evalNodesI(nodes: List[Node]): Int = {
    var stackV: List[Int] = Nil
    var nodesV = nodes

    while(nodesV != Nil) {
      nodesV match {
        case ValueNode(v) :: rest =>
          stackV = v :: stackV
          nodesV = rest
        case opNode :: rest =>
          val x = stackV.head
          stackV = stackV.tail
          val y = stackV.head
          stackV = stackV.tail
          opNode match {
            case AddNode =>
              stackV = y + x :: stackV
            case SubNode =>
              stackV = y - x :: stackV
            case MultNode =>
              stackV = y * x :: stackV
          }
          nodesV = rest
      }
    }
    stackV.head
  }



 val e =
    Add(Value(2),
      Mult(
        Value(3),
        Value(4)))


  val instructions = evalToNodes(e)

  val emptyStack = Nil
  val executedInstructions = evalNodes(instructions, emptyStack)

  println(evalNodes(evalToNodes(e), Nil))

  println("-----")
  println(evalNodesI(evalToNodes(e)))
}