I'm learning Scala and wrote a simple infix expression evaluator using the shunting yard algorithm. As opposed to the wikipedia example, this implementation evaluates the expression in place instead of converting it to a postfix notation. I'm mostly interested if I have used any Java idioms that would have better alternatives in Scala. I'm not too concerned about functional programming concepts at the moment as this is more of a syntax practice, but I will gladly accept any input. I've intentionally done some attempt to "clean code" by extracting more functions than what I usually do.
There is no input validation on literals. I have skipped it for now as I am considering adding support for variables and constants next.
The code:
import scala.collection.mutable
object InfixExpression {
/**
* Evaluate an expression.
*
* @param expression The expression, with operators and operands
* separated by whitespace.
*/
def evaluate(expression: String): BigDecimal =
processTokens(expression.split("\\s+") *)
private def processTokens(tokens: String*): BigDecimal =
val operands = mutable.Stack[BigDecimal]()
val operators = mutable.Stack[String]()
tokens.foreach(token => processToken(token, operands, operators))
operators.foreach(operator => processOperator(operator, operands))
if operands.size == 1 then
operands.pop()
else
throw new IllegalStateException("Not enough operators")
private def processToken(
token: String,
operands: mutable.Stack[BigDecimal],
operators: mutable.Stack[String]): Unit =
token match
case operator@("+" | "-" | "*" | "/" | "^") =>
processOperator(operator, operands, operators)
case "(" =>
processLeftParen(operands, operators)
case ")" =>
processRightParen(operands, operators)
case literal =>
processLiteral(literal, operands)
private def processOperator(
operator: String,
operands: mutable.Stack[BigDecimal],
operators: mutable.Stack[String]): Unit =
operators
.popWhile(op => op != "(" && precedence(op) > precedence(operator))
.foreach(op => processOperator(op, operands))
operators.push(operator)
private def processLeftParen(
operands: mutable.Stack[BigDecimal],
operators: mutable.Stack[String]): Unit =
operators.push("(")
private def processRightParen(
operands: mutable.Stack[BigDecimal],
operators: mutable.Stack[String]): Unit =
operators
.popWhile(op => op != "(")
.foreach(op => processOperator(op, operands))
if operators.isEmpty then
throw new IllegalStateException("Mismatched parenthesis")
else
operators.pop()
private def processLiteral(
literal: String,
operands: mutable.Stack[BigDecimal]): Unit =
operands.push(BigDecimal(literal))
private def processOperator(
operator: String,
operands: mutable.Stack[BigDecimal]): Unit =
if (operands.size < 2)
throw new IllegalStateException("Not enough operands")
val r = operands.pop() // Operands are in "reverse order" in the operands stack.
val l = operands.pop()
val result = operator match
case "+" => l + r
case "-" => l - r
case "*" => l * r
case "/" => l / r
case "^" => l.pow(r.toInt)
case "(" => throw new IllegalStateException("Mismatched parenthesis")
operands.push(result)
private def precedence(operator: String): Integer =
operator match
case "+" | "-" => 2
case "*" | "/" => 3
case "^" => 4
}
Usage:
InfixExpression.evaluate("2 ^ 64 - 1")