Thema: RPN-Rechner

  1. #1

    Registriert seit
    19.11.2011
    Beiträge
    496
    Thanked 412 Times in 268 Posts

    Standard RPN-Rechner

    Hallo,

    mal wieder eine Programmieraufgabe:
    Es geht um den Shunting-yard-Algorithmus, den es zu implementieren gilt. Der Algorithmus überführt einen Term aus der Infixnotation in die Reverse Polish Notation (RPN, deutsch: Umgekehrte Polnische Notation). Der überführte Term soll dann berechnet werden.

    Beispiel
    Eingabe (Array): "(", "22", "*", "(", "13", "-", "4.5", ")", ")", "/", "2", "+", "100"
    Ausgabe (RPN): "22", "13", "4.5", "-", "*", "2", "/", "100", "+"
    Ergebnis: 193.5

    Zusatz
    Die Eingabe erfolgt als Zeichenkette (Bsp: "(22 * (13 - 4.5)) / 2 + 100") und muss durch ein zusätzliches Verfahren erst entsprechend verarbeitet werden. Kurz: eine tokenize-Methode muss programmiert werden.


    Meine Lösung:
    Spoiler:Scala

    Code:
    object RPN {
    	private val ops: Map[String, Tuple2[(Double, Double) => Double, Int]] = 
    					 Map("+" -> ((a, b) => a + b, 1), "-" -> ((a, b) => b - a, 1),
    						 "*" -> ((a, b) => a * b, 2), "/" -> ((a, b) => b / a, 2))
    	
    	def fromInfix(s: String): String = {
    		val tokens = new scala.collection.mutable.ListBuffer[String]()
    		val opStack = new scala.collection.mutable.Stack[String]
    		for (i <- tokenize(s)) i match {
    			case digit if Character.isDigit(digit(0)) => tokens += digit
    			case op if ops contains op => {
    				if (opStack.length != 0) {
    					val cmpVal = if (opStack.head != "(") ops(opStack.head)._2 else 0
    					while (ops(op)._2 < cmpVal && opStack.length != 0) tokens += opStack.pop()
    				}
    				opStack push op
    			}
    			case lparen if lparen == "(" => opStack push lparen
    			case rparen if rparen == ")" => {
    				while (opStack.head != "(") tokens += opStack.pop()
    				if (opStack.length != 0) opStack.pop()
    			}
    			case dflt => println("Unbekanntes Zeichen: " + dflt)
    		}
    		while (opStack.length != 0) tokens += opStack.pop()
    		tokens mkString " "
    	}
    	
    	def compute(s: String) = {
    		val resStack = new scala.collection.mutable.Stack[Double]
    		tokenize(s).foreach(token => {
    			if (ops contains token) resStack push(ops(token)._1(resStack.pop(), resStack.pop()))
    			else resStack push token.toDouble
    		})
    		resStack.pop()
    	}
    	
    	private def tokenize(inp: String): Seq[String] = {
    		val tokens = new scala.collection.mutable.ListBuffer[String]()
    		var numbbuffer = ""
    		for (i <- inp) i match {
    			case digit if Character.isDigit(digit) || digit == '.' => numbbuffer = numbbuffer + digit.toString
    			case op if ops.contains(op.toString) || op == '(' || op == ')' || op == ' ' => {
    				if (numbbuffer != "") { tokens += numbbuffer; numbbuffer = "" }
    				tokens += op.toString
    			}
    			case dflt => if (!Character.isWhitespace(dflt)) println("Unbekanntes Zeichen: " + dflt)
    		}
    		if (numbbuffer != "") (tokens += numbbuffer).filter(_ != " ").toList 
    		else tokens.filter(_ != " ").toList
    	}
    }
    
    // Test
    println(RPN.compute(RPN.fromInfix("(22 * (13 - 4.5)) / 2 + 100"))) // 193.5
    Geändert von Mr. White (16.01.2013 um 18:04 Uhr)

Ähnliche Themen

  1. Rechner für Mutti
    Von Super Saiyajin im Forum Internet und Technik
    Antworten: 10
    Letzter Beitrag: 27.05.2013, 18:57
  2. Drucker > Kabel zum Rechner
    Von ElkosMED im Forum Hardware
    Antworten: 1
    Letzter Beitrag: 26.01.2013, 14:14
  3. Rechner Aufrüstung
    Von Valorax im Forum Kaufberatung
    Antworten: 8
    Letzter Beitrag: 26.12.2012, 12:23
  4. Neuer Rechner muss ran!
    Von Deniz27 im Forum Kaufberatung
    Antworten: 12
    Letzter Beitrag: 27.05.2012, 14:36
  5. Rechner
    Von rVs14 im Forum Hochsprachen
    Antworten: 13
    Letzter Beitrag: 06.09.2011, 17:43
Diese Seite nutzt Cookies, um das Nutzererlebnis zu verbessern. Klicken Sie hier, um das Cookie-Tracking zu deaktivieren.