107 lines
2.8 KiB
Ceylon
107 lines
2.8 KiB
Ceylon
import ceylon.collection {
|
|
|
|
ArrayList
|
|
}
|
|
|
|
abstract class Token(String|Integer data) of IntegerLiteral | Operator | leftParen | rightParen {
|
|
string => data.string;
|
|
}
|
|
class IntegerLiteral(shared Integer integer) extends Token(integer) {}
|
|
class Operator extends Token {
|
|
|
|
shared Integer precedence;
|
|
shared Boolean rightAssoc;
|
|
|
|
shared new plus extends Token("+") {
|
|
precedence = 2;
|
|
rightAssoc = false;
|
|
}
|
|
shared new minus extends Token("-") {
|
|
precedence = 2;
|
|
rightAssoc = false;
|
|
}
|
|
shared new times extends Token("*") {
|
|
precedence = 3;
|
|
rightAssoc = false;
|
|
}
|
|
shared new divides extends Token("/") {
|
|
precedence = 3;
|
|
rightAssoc = false;
|
|
}
|
|
shared new power extends Token("^") {
|
|
precedence = 4;
|
|
rightAssoc = true;
|
|
}
|
|
|
|
shared Boolean below(Operator other) =>
|
|
!rightAssoc && precedence <= other.precedence || rightAssoc && precedence < other.precedence;
|
|
}
|
|
object leftParen extends Token("(") {}
|
|
object rightParen extends Token(")") {}
|
|
|
|
|
|
shared void run() {
|
|
|
|
function shunt(String input) {
|
|
|
|
function tokenize(String input) =>
|
|
input.split().map((String element) =>
|
|
switch(element.trimmed)
|
|
case("(") leftParen
|
|
case(")") rightParen
|
|
case("+") Operator.plus
|
|
case("-") Operator.minus
|
|
case("*") Operator.times
|
|
case("/") Operator.divides
|
|
case("^") Operator.power
|
|
else IntegerLiteral(parseInteger(element) else 0)); // no error handling
|
|
|
|
value outputQueue = ArrayList<Token>();
|
|
value operatorStack = ArrayList<Token>();
|
|
|
|
void report(String action) {
|
|
print("``action.padTrailing(22)`` | ``" ".join(outputQueue).padTrailing(25)`` | ``" ".join(operatorStack).padTrailing(10)``");
|
|
}
|
|
|
|
print("input is ``input``\n");
|
|
print("Action | Output Queue | Operators' Stack
|
|
-----------------------|---------------------------|-----------------");
|
|
|
|
for(token in tokenize(input)) {
|
|
switch(token)
|
|
case(is IntegerLiteral) {
|
|
outputQueue.offer(token);
|
|
report("``token`` from input to queue");
|
|
}
|
|
case(leftParen) {
|
|
operatorStack.push(token);
|
|
report("``token`` from input to stack");
|
|
}
|
|
case(rightParen){
|
|
while(exists top = operatorStack.pop(), top != leftParen) {
|
|
outputQueue.offer(top);
|
|
report("``top`` from stack to queue");
|
|
}
|
|
}
|
|
case(is Operator) {
|
|
while(exists top = operatorStack.top, is Operator top, token.below(top)) {
|
|
operatorStack.pop();
|
|
outputQueue.offer(top);
|
|
report("``top`` from stack to queue");
|
|
}
|
|
operatorStack.push(token);
|
|
report("``token`` from input to stack");
|
|
}
|
|
}
|
|
while(exists top = operatorStack.pop()) {
|
|
outputQueue.offer(top);
|
|
report("``top`` from stack to queue");
|
|
}
|
|
return " ".join(outputQueue);
|
|
}
|
|
|
|
value rpn = shunt("3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3");
|
|
assert(rpn == "3 4 2 * 1 5 - 2 3 ^ ^ / +");
|
|
print("\nthe result is ``rpn``");
|
|
}
|