Symbolic Differentiator

symbolic_differentiator.go

package main

import (
	"fmt"
	"regexp"
	"strconv"
)

var polyRegex = regexp.MustCompile(`\s*(?P<coef>[+-]?[0-9]*)?\s*\*?((?P<var>[a-z])?\s*(\^(?P<pow>[+-]?[0-9]+))?)?\s*`)
var wsRegex = regexp.MustCompile(`\s+`)

type Term struct {
	Coefficient int64
	Exponent    int64
	Variable    string // for printing only
}

func (t Term) ToDebugString() string {
	return fmt.Sprintf("%#v", t)
}

func ParseTerm(s string) (Term, int, error) {
	indexes := polyRegex.FindStringIndex(s)
	if indexes == nil || indexes[0] != 0 {
		return Term{}, 0, fmt.Errorf("Invalid match for %s", s)
	}
	match := polyRegex.FindStringSubmatch(s)
	coefStr := match[polyRegex.SubexpIndex("coef")]
	powStr := match[polyRegex.SubexpIndex("pow")]
	varStr := match[polyRegex.SubexpIndex("var")]
	if coefStr == "" && varStr == "" {
		return Term{}, 0, fmt.Errorf("Both coefficient and variable are empty for %s", s)
	}
	var coef int64 = 1
	var err error
	if coefStr != "" {
		if coefStr == "-" {
			coef = -1
		} else {
			coef, err = strconv.ParseInt(coefStr, 10, 64)
			if err != nil {
				return Term{}, 0, err
			}
		}
	}

	var pow int64 = 1
	if varStr == "" {
		pow = 0
	}
	if powStr != "" {
		pow, err = strconv.ParseInt(powStr, 10, 64)
		if err != nil {
			return Term{}, 0, err
		}
	}

	t := Term{
		Coefficient: coef,
		Exponent:    pow,
		Variable:    varStr,
	}
	return t, indexes[1], nil
}

func ParsePolynomial(s string) ([]Term, error) {
	wss := wsRegex.ReplaceAllString(s, "")
	indexes := polyRegex.FindStringIndex(wss)
	if indexes == nil {
		return nil, nil
	}
	terms := make([]Term, 0)
	for {
		term, start, err := ParseTerm(wss)
		if err != nil || start == 0 {
			fmt.Println("ERR", err)
			return terms, err
		}
		fmt.Println(term.ToDebugString())
		terms = append(terms, term)
		wss = wss[start:]
		if len(wss) == 0 {
			break
		}
	}
	return terms, nil
}

func Differentiate(poly []Term) []Term {
	if poly == nil {
		return nil
	}
	diffPoly := make([]Term, 0)
	for _, t := range poly {
		var dc int64 = 0
		var dp int64 = 0
		if t.Variable != "" && t.Exponent != 0 {
			dp = t.Exponent - 1
			dc = t.Coefficient * t.Exponent
		}
		dt := Term{
			Coefficient: dc,
			Exponent:    dp,
			Variable:    t.Variable,
		}
		diffPoly = append(diffPoly, dt)
	}
	return diffPoly
}

func main() {
	for _, p := range []string{
		"12x^-12 + 123",
		"3*x^4 + 2x^2 + 23x + 123 - 7x^-1",
		"x",
		"-111",
		"x^23",
		"-3x",
		"-12x^7",
		"2x^4-6x^3-x+1",
		"-x+1",
	} {
		polynomial, err := ParsePolynomial(p)
		if err != nil {
			continue
		}
		fmt.Printf("%#v\n", Differentiate(polynomial))
	}
}