根据输入和输出，逆向栈的push和pop操作记录。例如，输入：abcd，输出：cdba，结果：[Push(a),Push(b),Push(c),Pop(c),Push(d),Pop(d),Pop(b),Pop(a)]

ReverseStackManipulation.scala

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)]