RPN実装サンプル
Jul 30, 2018 01:45 · 1078 words · 3 minute read
To RPN
import java.util.*
enum class ItemType(val weight: Int? = null) {
NUMBER(0),
LEFT_BRA,
RIGHT_BRA,
PLUS(2),
MINUS(2),
MULTI(1),
DIV(1)
}
data class Command(
val type: ItemType,
val text: String? = null
)
fun List<Command>.toRpn(): List<Command> {
val returnList: ArrayList<Command> = ArrayList()
val stack: Deque<Command> = ArrayDeque()
this.forEach {
when (it.type) {
ItemType.RIGHT_BRA -> {
val leftBraIndex =
stack.withIndex()
.firstOrNull {
it.value.type == ItemType.LEFT_BRA
}?.index
if (leftBraIndex != null) {
(0 until leftBraIndex).forEach {
returnList.add(stack.removeFirst())
}
stack.removeFirst()
}
}
else -> {
while (stack.isNotEmpty()) {
val latestStackWeight = stack.first().type.weight ?: break
val wight = it.type.weight ?: break
if (latestStackWeight > wight) break
else returnList.add(stack.removeFirst())
}
stack.addFirst(it)
}
}
}
returnList.addAll(stack)
return returnList
}
fun main(args: Array<String>) {
//sampleStart
var formula = listOf(
Command(ItemType.LEFT_BRA, "("),
Command(ItemType.NUMBER, "2"),
Command(ItemType.PLUS, "+"),
Command(ItemType.NUMBER, "5"),
Command(ItemType.RIGHT_BRA, ")"),
Command(ItemType.MULTI, "*"),
Command(ItemType.LEFT_BRA, "("),
Command(ItemType.NUMBER, "13"),
Command(ItemType.PLUS, "+"),
Command(ItemType.NUMBER, "4"),
Command(ItemType.RIGHT_BRA, ")")
)
println ("original: ${formula.map { it.text }.joinToString(" ")}")
println ("RPN: ${formula.toRpn().map { it.text }.joinToString(" ")}")
println ("")
formula = listOf(
Command(ItemType.NUMBER, "5"),
Command(ItemType.PLUS, "+"),
Command(ItemType.NUMBER, "2"),
Command(ItemType.MULTI, "*"),
Command(ItemType.NUMBER, "3")
)
println ("original: ${formula.map { it.text }.joinToString(" ")}")
println ("RPN: ${formula.toRpn().map { it.text }.joinToString(" ")}")
println ("")
formula = listOf(
Command(ItemType.LEFT_BRA, "("),
Command(ItemType.LEFT_BRA, "("),
Command(ItemType.NUMBER, "1"),
Command(ItemType.PLUS, "+"),
Command(ItemType.NUMBER, "2"),
Command(ItemType.RIGHT_BRA, ")"),
Command(ItemType.MULTI, "*"),
Command(ItemType.LEFT_BRA, "("),
Command(ItemType.NUMBER, "3"),
Command(ItemType.PLUS, "+"),
Command(ItemType.NUMBER, "4"),
Command(ItemType.RIGHT_BRA, ")"),
Command(ItemType.PLUS, "+"),
Command(ItemType.NUMBER, "5"),
Command(ItemType.RIGHT_BRA, ")"),
Command(ItemType.MULTI, "*"),
Command(ItemType.NUMBER, "6"),
Command(ItemType.RIGHT_BRA, ")")
)
println ("original: ${formula.map { it.text }.joinToString(" ")}")
println ("RPN: ${formula.toRpn().map { it.text }.joinToString(" ")}")
//sampleEnd
}
Evaluate RPN
import java.util.*
enum class ItemType(val weight: Int? = null) {
NUMBER(0),
LEFT_BRA,
RIGHT_BRA,
PLUS(2),
MINUS(2),
MULTI(1),
DIV(1)
}
data class Command(
val type: ItemType,
val text: String? = null
)
fun List<Command>.toRpn(): List<Command> {
val returnList: ArrayList<Command> = ArrayList()
val stack: Deque<Command> = ArrayDeque()
this.forEach {
when (it.type) {
ItemType.RIGHT_BRA -> {
val leftBraIndex =
stack.withIndex()
.firstOrNull {
it.value.type == ItemType.LEFT_BRA
}?.index
if (leftBraIndex != null) {
(0 until leftBraIndex).forEach {
returnList.add(stack.removeFirst())
}
stack.removeFirst()
}
}
else -> {
while (stack.isNotEmpty()) {
val latestStackWeight = stack.first().type.weight ?: break
val wight = it.type.weight ?: break
if (latestStackWeight > wight) break
else returnList.add(stack.removeFirst())
}
stack.addFirst(it)
}
}
}
returnList.addAll(stack)
return returnList
}
//sampleStart
fun List<Command>.calculate(): Double {
val stack: Deque<Double> = ArrayDeque()
this.forEach {
when (it.type) {
ItemType.NUMBER -> {
stack.addFirst(
it.text?.toDouble()
?: throw IllegalStateException()
)
}
ItemType.PLUS -> {
val a = stack.removeFirst()
val b = stack.removeFirst()
stack.addFirst(b + a)
}
ItemType.MINUS -> {
val a = stack.removeFirst()
val b = stack.removeFirst()
stack.addFirst(b - a)
}
ItemType.MULTI -> {
val a = stack.removeFirst()
val b = stack.removeFirst()
stack.addFirst(b * a)
}
ItemType.DIV -> {
val a = stack.removeFirst()
val b = stack.removeFirst()
stack.addFirst(b / a)
}
}
}
return stack.removeFirst()
}
fun main(args: Array<String>) {
var formula = listOf(
Command(ItemType.LEFT_BRA, "("),
Command(ItemType.NUMBER, "2"),
Command(ItemType.PLUS, "+"),
Command(ItemType.NUMBER, "5"),
Command(ItemType.RIGHT_BRA, ")"),
Command(ItemType.MULTI, "*"),
Command(ItemType.LEFT_BRA, "("),
Command(ItemType.NUMBER, "13"),
Command(ItemType.PLUS, "+"),
Command(ItemType.NUMBER, "4"),
Command(ItemType.RIGHT_BRA, ")")
)
println ("original: ${formula.map { it.text }.joinToString(" ")}")
println ("RPN: ${formula.toRpn().map { it.text }.joinToString(" ")}")
println ("calculate result: ${formula.toRpn().calculate()}")
println ("")
formula = listOf(
Command(ItemType.NUMBER, "5"),
Command(ItemType.PLUS, "+"),
Command(ItemType.NUMBER, "2"),
Command(ItemType.MULTI, "*"),
Command(ItemType.NUMBER, "3")
)
println ("original: ${formula.map { it.text }.joinToString(" ")}")
println ("RPN: ${formula.toRpn().map { it.text }.joinToString(" ")}")
println ("calculate result: ${formula.toRpn().calculate()}")
println ("")
formula = listOf(
Command(ItemType.LEFT_BRA, "("),
Command(ItemType.LEFT_BRA, "("),
Command(ItemType.NUMBER, "1"),
Command(ItemType.PLUS, "+"),
Command(ItemType.NUMBER, "2"),
Command(ItemType.RIGHT_BRA, ")"),
Command(ItemType.MULTI, "*"),
Command(ItemType.LEFT_BRA, "("),
Command(ItemType.NUMBER, "3"),
Command(ItemType.PLUS, "+"),
Command(ItemType.NUMBER, "4"),
Command(ItemType.RIGHT_BRA, ")"),
Command(ItemType.PLUS, "+"),
Command(ItemType.NUMBER, "5"),
Command(ItemType.RIGHT_BRA, ")"),
Command(ItemType.MULTI, "*"),
Command(ItemType.NUMBER, "6"),
Command(ItemType.RIGHT_BRA, ")")
)
println ("original: ${formula.map { it.text }.joinToString(" ")}")
println ("RPN: ${formula.toRpn().map { it.text }.joinToString(" ")}")
println ("calculate result: ${formula.toRpn().calculate()}")
}
//sampleEnd
More complex
import kotlin.math.*
import java.util.*
enum class ItemType(val weight: Int? = null) {
NUMBER(0),
PI(0),
E(0),
LEFT_BRA,
RIGHT_BRA,
PLUS(4),
MINUS(4),
MULTI(3),
DIV(3),
POW(2),
MOD(2),
SQRT(1),
SIN(1),
COS(1),
TAN(1),
A_SIN(1),
A_COS(1),
A_TAN(1),
LN(1),
LOG10(1),
LOG2(1),
ABS(1)
}
data class Command(
val type: ItemType,
val text: String? = null
)
fun List<Command>.toRpn(): List<Command> {
val returnList: ArrayList<Command> = ArrayList()
val stack: Deque<Command> = ArrayDeque()
this.forEach {
when (it.type) {
ItemType.RIGHT_BRA -> {
val leftBraIndex =
stack.withIndex()
.firstOrNull {
it.value.type == ItemType.LEFT_BRA
}?.index
if (leftBraIndex != null) {
(0 until leftBraIndex).forEach {
returnList.add(stack.removeFirst())
}
stack.removeFirst()
}
}
else -> {
while (stack.isNotEmpty()) {
val latestStackWeight = stack.first().type.weight ?: break
val wight = it.type.weight ?: break
if (latestStackWeight > wight) break
else returnList.add(stack.removeFirst())
}
stack.addFirst(it)
}
}
}
returnList.addAll(stack)
return returnList
}
fun List<Command>.calculate(): Double {
val stack: Deque<Double> = ArrayDeque()
this.forEach {
when (it.type) {
ItemType.NUMBER -> {
stack.addFirst(
it.text?.toDouble()
?: throw IllegalStateException()
)
}
ItemType.PI -> {
stack.addFirst(PI)
}
ItemType.E -> {
stack.addFirst(E)
}
ItemType.PLUS -> {
val a = stack.removeFirst()
val b = stack.removeFirst()
stack.addFirst(b + a)
}
ItemType.MINUS -> {
val a = stack.removeFirst()
val b = stack.removeFirst()
stack.addFirst(b - a)
}
ItemType.MULTI -> {
val a = stack.removeFirst()
val b = stack.removeFirst()
stack.addFirst(b * a)
}
ItemType.DIV -> {
val a = stack.removeFirst()
val b = stack.removeFirst()
val preResult = b.toDouble() / a.toDouble()
stack.addFirst(b / a)
}
ItemType.POW -> {
val a = stack.removeFirst()
val b = stack.removeFirst()
stack.addFirst(b.pow(a))
}
ItemType.MOD -> {
val a = stack.removeFirst()
val b = stack.removeFirst()
stack.addFirst(b % a)
}
ItemType.SQRT -> {
val a = stack.removeFirst()
stack.addFirst(sqrt(a))
}
ItemType.COS -> {
val a = stack.removeFirst()
stack.addFirst(cos(a))
}
ItemType.SIN -> {
val a = stack.removeFirst()
stack.addFirst(sin(a))
}
ItemType.TAN -> {
val a = stack.removeFirst()
stack.addFirst(tan(a))
}
ItemType.A_COS -> {
val a = stack.removeFirst()
stack.addFirst(acos(a))
}
ItemType.A_SIN -> {
val a = stack.removeFirst()
stack.addFirst(asin(a))
}
ItemType.A_TAN -> {
val a = stack.removeFirst()
stack.addFirst(atan(a))
}
ItemType.LN -> {
val a = stack.removeFirst()
stack.addFirst(ln(a))
}
ItemType.LOG10 -> {
val a = stack.removeFirst()
stack.addFirst(log10(a))
}
ItemType.LOG2 -> {
val a = stack.removeFirst()
stack.addFirst(log2(a))
}
ItemType.ABS -> {
val a = stack.removeFirst()
stack.addFirst(abs(a))
}
}
}
return stack.removeFirst()
}
fun main(args: Array<String>) {
//sampleStart
var formula = listOf(
Command(ItemType.LEFT_BRA, "("),
Command(ItemType.SQRT, "√"),
Command(ItemType.NUMBER, "9"),
Command(ItemType.PLUS, "+"),
Command(ItemType.NUMBER, "5"),
Command(ItemType.RIGHT_BRA, ")"),
Command(ItemType.MULTI, "*"),
Command(ItemType.LEFT_BRA, "("),
Command(ItemType.NUMBER, "13"),
Command(ItemType.MOD, "%"),
Command(ItemType.NUMBER, "3"),
Command(ItemType.PLUS, "+"),
Command(ItemType.NUMBER, "4"),
Command(ItemType.RIGHT_BRA, ")"),
Command(ItemType.MULTI, "*"),
Command(ItemType.SIN, "sin"),
Command(ItemType.LEFT_BRA, "("),
Command(ItemType.PI, "π"),
Command(ItemType.MULTI, "*"),
Command(ItemType.NUMBER, "3"),
Command(ItemType.DIV, "/"),
Command(ItemType.NUMBER, "2"),
Command(ItemType.RIGHT_BRA, ")")
)
println ("original: ${formula.map { it.text }.joinToString(" ")}")
println ("RPN: ${formula.toRpn().map { it.text }.joinToString(" ")}")
println ("calculate result: ${formula.toRpn().calculate()}")
//sampleEnd
}
From: Flical