Commits

Eric Roshan Eisner committed a4676b3 Draft

parser

  • Participants
  • Parent commits 585f360

Comments (0)

Files changed (2)

+package units
+
+import "strconv"
+
+type parseError string
+
+func (err parseError) Error() string {
+	return string(err)
+}
+
+// Thing that eats values and operators in a postfix order.
+type postfixConsumer struct {
+	stack []Value
+}
+
+func (c *postfixConsumer) eatValue(v Value) {
+	c.stack = append(c.stack, v)
+}
+
+func (c *postfixConsumer) eatOperator(op string) (err error) {
+	// All operators are 2 argument infix, get the args up front.
+	if len(c.stack) < 2 {
+		return parseError("Not enough arguments for operator " + op)
+	}
+	b := c.stack[len(c.stack)-1]
+	a := c.stack[len(c.stack)-2]
+	c.stack = c.stack[:len(c.stack)-2]
+
+	// Catch panics from adds and subtracts and turn them into errors.
+	defer func() {
+		if x := recover(); x != nil {
+			s, _ := x.(string)
+			err = parseError(s)
+		}
+	}()
+
+	var v Value
+	switch op {
+	case "*":
+		v = a.Mul(b)
+	case "/":
+		v = a.Div(b)
+	case "+":
+		v = a.Add(b)
+	case "-":
+		v = a.Sub(b)
+	default:
+		return parseError("Unrecognized operator " + op)
+	}
+
+	c.stack = append(c.stack, v)
+	return nil
+}
+
+func (c *postfixConsumer) getValue() (v Value, err error) {
+	if len(c.stack) == 0 {
+		err = parseError("No values were parsed.")
+	} else if len(c.stack) > 1 {
+		err = parseError("Parser ended up with too many values.")
+	} else {
+		v = c.stack[0]
+	}
+	return
+}
+
+type stringStack struct {
+	stack []string
+}
+
+func (s *stringStack) Empty() bool {
+	return len(s.stack) == 0
+}
+
+func (s *stringStack) Last() string {
+	return s.stack[len(s.stack)-1]
+}
+
+func (s *stringStack) Push(in string) {
+	s.stack = append(s.stack, in)
+}
+
+func (s *stringStack) Pop() string {
+	item := s.Last()
+	s.stack = s.stack[:len(s.stack)-1]
+	return item
+}
+
+func precedence(op string) int {
+	switch op {
+	case "*", "/":
+		return 2
+	case "+", "-":
+		return 1
+	}
+	return 0
+}
+
+type ParseOutput struct {
+	Value       Value
+	Conversion  bool
+	ConvertUnit string
+}
+
+func (out *ParseOutput) String() string {
+	if out.Conversion {
+		unitValue, _ := parseUnit(out.ConvertUnit)
+		num := out.Value.Div(unitValue).num
+		return strconv.FormatFloat(num, 'g', 6, 64) + out.ConvertUnit
+	}
+	return out.Value.String()
+}
+
+func Parse(src string) (out *ParseOutput, err error) {
+	tokens, err := tokenize(src)
+	if err != nil {
+		return nil, err
+	}
+
+	out = new(ParseOutput)
+	if len(tokens) >= 2 && tokens[len(tokens)-2] == "in" {
+		if _, ok := parseUnit(tokens[len(tokens)-1]); ok {
+			out.Conversion = true
+			out.ConvertUnit = tokens[len(tokens)-1]
+			tokens = tokens[:len(tokens)-2]
+		}
+	}
+
+	// Convert token stream into postfix order and feed to the consumer for
+	// evaluation. Uses the Shunting-yard algorithm.
+	var opstack stringStack
+	var consumer postfixConsumer
+
+	for i := 0; i < len(tokens); i += 1 {
+		token := tokens[i]
+		switch token {
+		case "*", "/", "+", "-":
+			for !opstack.Empty() &&
+				precedence(token) <= precedence(opstack.Last()) {
+				err = consumer.eatOperator(opstack.Pop())
+				if err != nil {
+					return nil, err
+				}
+			}
+			opstack.Push(token)
+		case "(":
+			opstack.Push(token)
+		case ")":
+			for !opstack.Empty() && opstack.Last() != "(" {
+				err = consumer.eatOperator(opstack.Pop())
+				if err != nil {
+					return nil, err
+				}
+			}
+			if opstack.Empty() || opstack.Last() != "(" {
+				err = parseError("No matching open paren.")
+				return nil, err
+			}
+			opstack.Pop() // Remove the open paren.
+		default:
+			// Try to parse as a float
+			if num, e := strconv.ParseFloat(token, 64); e == nil {
+				v := Value{num, Unitless}
+				// Peek at the next token to see if it's a unit.
+				if i+1 < len(tokens) {
+					u, ok := parseUnit(tokens[i+1])
+					if ok {
+						i += 1
+						v = v.Mul(u)
+					}
+				}
+				consumer.eatValue(v)
+			} else {
+				// this is an unrecognized unit or string blob out of place
+				return nil, parseError("Unexpected string `" + token + "` in input.")
+			}
+		}
+	}
+
+	for !opstack.Empty() {
+		if opstack.Last() == "(" {
+			return nil, parseError("No matching close paren.")
+		}
+		err = consumer.eatOperator(opstack.Pop())
+		if err != nil {
+			return nil, err
+		}
+	}
+
+	out.Value, err = consumer.getValue()
+	if err != nil {
+		return nil, err
+	}
+	return
+}
 		}
 	}
 }
+
+var parsingTable = []struct {
+	src  string
+	fail bool
+	out  string
+}{
+	{"1m+200mm", false, "1.2m"},
+	{"1m * 2", false, "2m"},
+	{"1in in mm", false, "25.4mm"},
+	{"1J + 1N*1m - 1W*1s", false, "1J"},
+	{"3600J/(.5h+1800s)", false, "1W"},
+	{"3+4*2/(1-5)", false, "1"},
+
+	{"", true, ""},
+	{"(3+2) (2*3)", true, ""},
+	{"45mm + 22s", true, ""},
+	{"(5*2", true, ""},
+	{"1+2)", true, ""},
+	{"10J m", true, ""},
+	{"3+", true, ""},
+	{"*3", true, ""},
+}
+
+func TestParsing(t *testing.T) {
+	for _, entry := range parsingTable {
+		out, err := Parse(entry.src)
+
+		if entry.fail && err == nil {
+			t.Errorf("Parsing %q: expected error, but got no error.")
+		}
+		if !entry.fail && err != nil {
+			t.Errorf("Parsing %q: expected no error, got %q",
+				entry.src, err.Error())
+		}
+
+		if err != nil {
+			continue
+		}
+		outstr := out.String()
+		if entry.out != outstr {
+			t.Errorf("Parsing %q: expected %q, got %q",
+				entry.src, entry.out, outstr)
+		}
+	}
+}