Created
March 29, 2011 09:23
-
-
Save songpp/892075 to your computer and use it in GitHub Desktop.
根据输入和输出,逆向栈的push和pop操作记录。例如,输入:abcd,输出:cdba,结果:[Push(a),Push(b),Push(c),Pop(c),Push(d),Pop(d),Pop(b),Pop(a)]
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package algrithsm | |
import collection.mutable.Stack | |
import org.slf4j.{LoggerFactory, Logger} | |
import Console._ | |
/** | |
* User: flower | |
* Date: 11-3-29 | |
* Time: 下午3:04 | |
* Description: | |
*/ | |
object ReverseStackManipulation { | |
private val log : Logger = LoggerFactory.getLogger(getClass) | |
type T = Char | |
val input :String = "abcdefgh" | |
val output :String = "edcfgbha" | |
val indexedInput = input.zipWithIndex | |
val indexedOutput = output map { | |
c => | |
(c, input.findIndexOf(c ==)) | |
} | |
def reverse = { | |
def runPushOfARangeOfElements(coll: IndexedSeq[(Char, Int)], | |
from: Int, | |
to: Int) { | |
log.debug("from {} to {}",from,to) | |
val elements = coll.slice(from + 1,to + 1) | |
val last = elements.apply(elements.size - 1) | |
log.debug("elements size {}, last {}",elements.size,last._1) | |
elements foreach { e => appendOp(Push(e._1)) } | |
appendOp(Pop(last._1)) | |
} | |
val (firstChar, firstElementIndex) = indexedOutput.head | |
var current = 0 | |
var lastPushedIndex = -1 | |
while (current < indexedOutput.size) { | |
val (c, idx) = indexedOutput(current) | |
if (idx >= firstElementIndex) { | |
runPushOfARangeOfElements(indexedInput, lastPushedIndex, idx) | |
} | |
else { | |
appendOp(Pop(c)) | |
} | |
if(lastPushedIndex < idx) | |
lastPushedIndex = idx | |
current += 1 | |
} | |
dumpResult | |
} | |
def dumpResult = { | |
println("input is : %s".format(input)) | |
println("output is : %s".format(output)) | |
println("result is : %s".format(operation.reverse.mkString("[", ",", "]"))) | |
} | |
abstract class Op(c: Char) | |
case class Push(c: Char) extends Op(c) | |
case class Pop(respect: Char) extends Op(respect) | |
var stack: Stack[Char] = new Stack | |
var operation: List[Op] = Nil | |
def appendOp(op: Op) { | |
op match { | |
case Push(v) => | |
stack.push(v) | |
case Pop(respect) => | |
val top = stack.pop() | |
if (respect != top) { | |
dumpResult | |
throw new Error(("output you given is not correct " + | |
"respected Op is %s but current stack top is %s").format(op, top)) | |
} | |
} | |
operation = op :: operation | |
} | |
def main(args: Array[String]) { | |
reverse | |
} | |
} |
input is : abcdefg
output is : efdcgba
result is : [Push(a),Push(b),Push(c),Push(d),Push(e),Pop(e),Push(f),Pop(f),Pop(d),Pop(c),Push(g),Pop(g),Pop(b),Pop(a)]
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
input is : abcd
output is : cdba
result is : [Push(a),Push(b),Push(c),Pop(c),Push(d),Pop(d),Pop(b),Pop(a)]