RpnParser.java

package lombok.parboiled;

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;

import org.parboiled.BaseActions;
import org.parboiled.BaseParser;
import org.parboiled.Parboiled;
import org.parboiled.Rule;
import org.parboiled.common.Function;
import org.parboiled.common.StringUtils;
import org.parboiled.support.ParseTreeUtils;
import org.parboiled.support.ParsingResult;
import org.parboiled.trees.Printability;

public class RpnParser extends BaseParser<RpnParser.Node, RpnParser.RpnActions> {
	public static class Node {
		private final BigDecimal number;
		private final char operator;
		private final List<BigDecimal> result;
		private final List<String> warnings;
		
		public boolean isOperator() {
			return operator != '\0';
		}
		
		public boolean isNumber() {
			return result == null && operator == '\0';
		}
		
		public BigDecimal getNumber() {
			return number;
		}
		
		public char getOperator() {
			return operator;
		}
		
		public String getWarnings() {
			if (warnings.isEmpty()) return "";
			if (warnings.size() == 1) return warnings.get(0);
			return StringUtils.join(warnings, "\n---\n");
		}
		
		public List<BigDecimal> getResult() {
			return result;
		}
		
		private Node(BigDecimal number, char operator, List<BigDecimal> result, List<String> warnings) {
			this.number = number;
			this.operator = operator;
			this.result = result;
			this.warnings = warnings;
		}
		
		public static Node number(BigDecimal number) {
			return new Node(number, '\0', null, null);
		}
		
		public static Node operator(String op) {
			return new Node(null, op == null || op.isEmpty() ? '?' : op.charAt(0), null, null);
		}
		
		public static Node result(List<BigDecimal> result, List<String> warnings) {
			return new Node(null, '\0', result == null ? Collections.<BigDecimal>emptyList() : result, warnings == null ? Collections.<String>emptyList() : warnings);
		}
		
		@Override public String toString() {
			if (isOperator()) return String.valueOf(operator);
			if (isNumber()) return number == null ? "NaN" : number.toString();
			return result.toString();
		}
	}
	
	public static class RpnActions extends BaseActions<Node> {
		public Node toBigDecimal(String lastText) {
			if (lastText == null || lastText.isEmpty()) return Node.number(null);
			try {
				return Node.number(new BigDecimal(lastText));
			} catch (Exception e) {
				return Node.number(null);
			}
		}
		
		public Node runStack(List<Node> values) {
			Stack<BigDecimal> stack = new Stack<BigDecimal>();
			List<String> warnings = new ArrayList<String>();
			int idx = -1;
			for (Node v : values) {
				idx++;
				if (v.isNumber()) stack.push(v.getNumber());
				else if (v.isOperator()) {
					BigDecimal left, right;
					right = stack.isEmpty() ? null : stack.pop();
					left = stack.isEmpty() ? null : stack.pop();
					if (left == null && right == null) {
						warnings.add(String.format(
								"0 operands instead of the expected 2 processing %s at %d", v.getOperator(), idx));
					} else if (left == null) {
						stack.push(right);
						warnings.add(String.format(
								"1 operand (right: %s) instead of the expected 2 processing %s at %d", right, v.getOperator(), idx));
					} else if (right == null) {
						stack.push(left);
						warnings.add(String.format(
								"1 operand (left: %s) instead of the expected 2 processing %s at %d", left, v.getOperator(), idx));
					} else switch (v.getOperator()) {
					case '+':
						stack.push(left.add(right));
						break;
					case '-':
						stack.push(left.subtract(right));
						break;
					case '*':
						stack.push(left.multiply(right));
						break;
					case '/':
						stack.push(left.divide(right));
						break;
					case '^':
						try {
							stack.push(left.pow(right.intValueExact()));
						} catch (ArithmeticException e) {
							stack.push(BigDecimal.ONE);
							warnings.add(String.format(
									"Right side of power operator is %s (left: %s); expected an integer in the 32-bit range. Resuming with dummy result '1' at %d",
									right, left, idx));
						}
						break;
					default:
						stack.push(BigDecimal.ZERO);
						warnings.add(String.format("Unknown operator: %s; pushing dummy result '0' at %d", v.getOperator(), idx));
					}
				}
			}
			
			return Node.result(new ArrayList<BigDecimal>(stack), warnings);
		}
		
		public Node toOperator(String op) {
			return Node.operator(op);
		}
	}
	
	public static void main(String[] args) {
		RpnParser parser = Parboiled.createParser(RpnParser.class);
		Scanner s = new Scanner(System.in);
		System.out.println("RPN Parser: Enter any reverse polish notation string and I'll parse and calculate it for you.");
		while (true) {
			String in = s.nextLine();
			if (in.isEmpty()) return;
			ParsingResult<Node> result = parser.parse(parser.operation(), in);
			System.out.println(ParseTreeUtils.printNodeTree(result, new Function<org.parboiled.Node<Node>, Printability>() {
				@Override public Printability apply(org.parboiled.Node<Node> from) {
					if (from.getLabel() != null) {
						if (from.getLabel().matches("^(\".*\")|ws|wsChar$")) return Printability.Print;
					}
					
					return Printability.PrintAndDescend;
				}
			}));
			List<BigDecimal> output = result.parseTreeRoot.getValue().getResult();
			if (result.hasErrors()) {
				System.out.println(StringUtils.join(result.parseErrors, "---\n"));
			}
			System.out.println(result.parseTreeRoot.getValue().getWarnings());
			System.out.println("Result: " + (output.size() == 1 ? output.get(0) : output.toString()));
		}
	}
	
	public RpnParser() {
		super(Parboiled.createActions(RpnActions.class));
	}
	
	public Rule operation() {
		return sequence(
				optional(zeroOrMore(wsChar())),
				zeroOrMore(atom()).label("sequenceOfAtoms"),
				eoi(),
				SET(actions.runStack(VALUES("s/a"))));
	}
	
	public Rule atom() {
		return firstOf(number(), binarySymbol());
	}
	
	public Rule binarySymbol() {
		return enforcedSequence(
				firstOf(ch('+'), ch('-'), ch('*'), ch('/'), ch('^')),
				SET(actions.toOperator(LAST_TEXT())),
				optional(ws()));
	}
	
	public Rule number() {
		return sequence(
			sequence(
				optional(ch('-').label("minus")),
				firstOf(
					enforcedSequence(ch('.'), oneOrMore(digit())).label("dotNumber"),
					enforcedSequence(oneOrMore(digit()).label("digits"),
						optional(enforcedSequence(ch('.'), oneOrMore(digit())).label("dotNumber")))),
					optional(enforcedSequence(charIgnoreCase('E'), optional(ch('-').label("minus")), oneOrMore(digit())).label("exponent"))),
			SET(actions.toBigDecimal(LAST_TEXT())),
			optional(ws()));
	}
	
	public Rule ws() {
		return firstOf(
			enforcedSequence(ch(','), zeroOrMore(wsChar()).label("wsChars")),
			oneOrMore(wsChar()).label("wsChars"));
	}
	
	public Rule wsChar() {
		return firstOf(' ', '\t', '\f', "\r\n", '\r', '\n');
	}
	
	public Rule digit() {
		return charRange('0', '9');
	}
}