Skip to content

Instantly share code, notes, and snippets.

@rrampage
Last active October 10, 2023 22:32
Show Gist options
  • Save rrampage/f0c228fb7ecde82b3dd170246263e231 to your computer and use it in GitHub Desktop.
Save rrampage/f0c228fb7ecde82b3dd170246263e231 to your computer and use it in GitHub Desktop.
Symbolic Differentiator
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))
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment