Как подойти к упрощению выражения (и, или, не) в Scala?

Question

Я в затруднении с тем, как решить мою проблему. У меня есть домашнее задание, в котором мне нужно упростить выражения, используя правила, изложенные профессором. Мне нужно взять строки из выражений:

"(and(x x))" 
"(or (and x z) y)" 
"(and (or z (not x))(or e a))" 

и упростить их с помощью правил:

(or x nil) => x; 
(or nil x) => x; 
(or 1 x) => 1; 
(or x 1) => 1; 
(and x nil) => nil; 
(and nil x) => nil; 
(and x 1) => x; 
(and 1 x) => x; 
(not nil) => 1; 
(not 1) => nil; 
(not (and x y)) => (or (not x) (not y)); 
(not (or x y)) => (and (not x) (not y)); 

я решил взять выражения в точной форме, что она выше (не может быть иначе), и разобрать его в массив, так что в каждом индексе, например, это будет выглядеть следующим образом:

and or x y z //ArrayBuffer[String] 

затем я использую рекурсивную функцию, которая проверяет левые и правые выражения, пока он не получит СИМПЛИ выражение. Моя проблема заключается не в правилах, как я понял это. Я по существу есть 3 случая сделано, которые:

"(and z (or x y)" // the case when the left symbol is simple but the right side must be recursed 
"(and (or x y) z)" // case when the right symbol is simple but the right side must be recursed 
"(and x y)" // simple case where no recursion is necessary 

я пропускаю случай, когда обе левые и правые символы должны быть Рекурсия для того, чтобы получить эти упрощенные символы. У меня нет возможности узнать, когда они заканчиваются или начинаются, и там может быть много случаев, в которых он должен быть Рекурсия даже в тех внутренних выражениях:

"(and (or (and x y) z)(or x a))" 
"(and (or (and x y) z)(or (and y z) a))" 

Я подумал о том, как это может быть сделано в эффективный способ с текущей реализацией, который у меня есть, но пока ничего не получил. Я прошу совета относительно того, как это сделать. Я не предоставляю никакого кода, поскольку я хотел бы сделать это самостоятельно, просто нужно подтолкнуть в правильном направлении. Если требуется уточнение, спросите, и я сделаю это. Еще раз спасибо!

Answer 1

and or x y z //ArrayBuffer[String] 

Я бы не стал представлять такое выражение. Хотя можно однозначно получить структуру выражения в префиксном понятии, это не так просто, как когда у вас есть рекурсивная структура.

Вы должны вместо этого представлять выражение с рекурсивно определенной иерархией классов. Не указывая слишком много деталей, у вас, вероятно, будет интерфейс (Trait или аннотация Class) и разработчики этого интерфейса, которые зависят от количества аргументов: один для выражений с тремя частями (например, ((or, x, y) или (and, (or x y), z))), один для выражения с двумя частями (как (not, x)), и один для выражений с одной стороны (как x, y, z, nil, и т.д.).

Тогда ваша процедура упрощения становится один большой метод сопоставления с образцом, который может называть себя рекурсивно пересечь синтаксическое дерево выражения:

def simplify(expression: ExpressionIterface) = 
    expression match { 
     case /* pattern */ => /* result, possibly with a recursive call to simplify */ 
     ... 
    } 

EDIT: Преобразование ArrayBuffer[String] в ваши классы может быть выполнено с помощью простой рекурсивной синтаксической разборки, поскольку вы знаете, сколько аргументов должно быть связано с каждым оператором. Вы можете пересечь буфер, и каждый раз, когда вы видите или or, вы начинаете создавать выражение из трех частей, каждый раз, когда вы видите not, вы начинаете создавать выражение из 2 частей, и вы создаете выражение из 1 части для что-нибудь еще.

Answer 2

Вот простая реализация для решения DHG в:

package solve 

sealed trait Expr 
case class Not(e:Expr) extends Expr 
case class And(e1:Expr, e2:Expr) extends Expr 
case class Or(e1:Expr, e2:Expr) extends Expr 
case class Idn(v:String) extends Expr 
object Solve extends App { 
    def prep(s:String):List[String] = 
    s.replaceAll("[()]+"," ").split(" ").filter(_.size > 0).toList 
    def parse(l:List[String]):Expr = 
    parseI(l) match { 
     case (e,Nil) => e 
     case _ => throw new Exception("malformed exception") 
    } 
    def parseI(l:List[String]):(Expr,List[String]) = 
    l match { 
     case "not" :: rest => 
     val (e, rem) = parseI(rest) 
     (Not(e), rem) 
     case "and" :: rest => 
     val (e1, rem) = parseI(rest) 
     val (e2, rem2) = parseI(rem) 
     (And(e1,e2), rem2) 
     case "or" :: rest => 
     val (e1, rem) = parseI(rest) 
     val (e2, rem2) = parseI(rem) 
     (Or(e1,e2), rem2) 
     case i :: rest => 
     (Idn(i), rest) 
     case Nil => throw new Exception 
    } 
    def simplify(e:Expr):Expr = { 
    e match { 
     case Or(x,Idn("nil")) => simplify(x) 
     case Or(Idn("1"),x) => Idn("1") 
     case Or(x,y) => Or(simplify(x),simplify(y)) 
     case x => x 
    } 
    } 
} 

И тест для этого:

import org.scalatest.FunSuite 
import org.scalatest.matchers.ShouldMatchers 
import solve._ 
import Solve._ 

class SolveTest extends FunSuite with ShouldMatchers { 
    test ("prepare expression") { 
    prep("(and(x x))") should equal (List("and","x","x")) 
    } 
    test ("parse expressions") { 
    parse(prep("(and(x x))")) should equal (And(Idn("x"), Idn("x"))) 
    parse(prep("(or (and x z) y)")) should equal (Or(And(Idn("x"), Idn("z")), Idn("y"))) 
    parse(prep("(and (or z (not x))(or e a))")) should equal (And(Or(Idn("z"),Not(Idn("x"))),Or(Idn("e"),Idn("a")))) 
    } 
    test ("simplification") { 
    simplify(parse(prep("(or (and x z) nil)"))) should equal (And(Idn("x"),Idn("z"))) 
    } 
} 

Answer 3

Я думаю, что это покрывается в Scala by Example book available as a PDF с лестницей сайта Ланг (см Глава 7). Мое предложение состояло в том, чтобы использовать классы case для представления ваших выражений, а затем использовать сопоставление шаблонов для упрощения выражений:

Для начала давайте определим признак выражения, который будет использоваться для представления всех видов выражений.

scala> trait Expr { def simplify:Expr = this } 
defined trait Expr 

Здесь я позволил черта Expr реализовать simplify метод по умолчанию, который просто возвращает объект, который расширяет черту. Так давайте добавим несколько простых выражений:

scala> case object True extends Expr 
defined module True 

scala> case object False extends Expr 
defined module False 

scala> case class Var(name:String) extends Expr { override def toString = name } 
defined class Var 

True и False будет представлять 1 и nil в вашем примере. Var будет использоваться для представления переменной, которая еще не имеет значения истины, например. x, y, a и b в вашем примере. Вар также переоценивает метод toString, чтобы сделать распечатку немного красивее :)

Теперь немного сложнее ситуация с и/или. Позволяет определить их как:

scala> case class And(a:Expr, b:Expr) extends Expr { 
    | override def simplify = (a.simplify, b.simplify) match { 
    | case (True,x) => x 
    | case (x,True) => x 
    | case (False,x) => False 
    | case (x,False) => False 
    | case (x,y) => And(x,y) 
    | } 
    | } 
defined class And 

scala> case class Or(a:Expr, b:Expr) extends Expr { 
    | override def simplify = (a.simplify, b.simplify) match { 
    | case (True,x) => True 
    | case (x,True) => True 
    | case (False,x) => x 
    | case (x,False) => x 
    | case (x,y) => Or(x,y) 
    | } 
    | } 
defined class Or 

And и Or как переопределить метод simplify в Expr черты и вернуться упрощенные версии самих и их subexressions. Теперь они могут быть использованы для построения выражений, наряду с простыми True, False и Var выражений:

scala> val X = Var("X"); val Y = Var("Y"); val A = Var("A"); val B = Var("B") 
X: Var = X 
Y: Var = Y 
A: Var = A 
B: Var = B 

scala> And(X, True).simplify 
res10: Expr = X 

scala> And(X, And(Y, False)).simplify 
res11: Expr = False 

scala> And(X, Or(Y, False)).simplify 
res12: Expr = And(X,Y) 

scala> Or(True, And(X, Or(Y, False))).simplify 
res13: Expr = True 

Наконец мы добавим выражение для: не

scala> case class Not(a:Expr) extends Expr { 
    | override def simplify = a.simplify match { 
    | case True => False 
    | case False => True 
    | case And(x,y) => Or(Not(x),Not(y)) 
    | case Or(x,y) => And(Not(x),Not(y)) 
    | case Not(x) => x 
    | case x => Not(x) 
    | } 
    | } 
defined class Not 

Теперь мы можем представить выражения в вашем пример. Однако для некоторого выражения этот класс не будет делать полное упрощение, например.

scala> Not(Or(Not(X),Y)).simplify 
res41: Expr = And(Not(Not(X)),Not(Y)) 

Таким образом, мы могли бы определить рекурсивную функцию в Not, который пытается упростить выражение, пока он не может упростить его больше:

scala> case class Not(a:Expr) extends Expr { 
    | override def simplify = recursiveSimplify(a, a) 
    | private def recursiveSimplify(curExpr:Expr, lastExpr:Expr):Expr = if(curExpr != lastExpr) { 
    | val newExpr = curExpr.simplify match { 
    | case True => False 
    | case False => True 
    | case Var(x) => Not(Var(x)) 
    | case Not(x) => x 
    | case And(x,y) => Or(Not(x), Not(y)) 
    | case Or(x,y) => And(Not(x), Not(y)) 
    | } 
    | recursiveSimplify(newExpr, curExpr) 
    | } else { 
    | lastExpr 
    | } 
    | } 
defined class Not 

Теперь ранее выражение упрощается:

scala> Not(Or(Not(X),Y)).simplify 
res42: Expr = Or(Not(X),Y)