-1

I am developing an application with the C ++ programming language to graph mathematical functions, the user writes the function, the domain and the range. I am using the Win32 API together with Direct2D, but I don't know how to get the program to graph the selected functions by the user. For example, the user enters the function "f (x) = x + 1", and the program should graph a line. Are there any algorithms that can be implemented to analyze the function entered and thus be able to graph it?

Jabberwocky
  • 48,281
  • 17
  • 65
  • 115
Franco Cortes
  • 35
  • 2
  • 2
    Does this answer your question? [parsing math expression in c++](https://stackoverflow.com/questions/11703082/parsing-math-expression-in-c) – Louis Go Apr 23 '20 at 03:10
  • 4
    "[This is the sort of thing we call “business logic”: The part of the program that is devoted to doing the things the program does, that only the program knows how to do. The operating system doesn’t know how your business logic works; that’s entirely within you control as the developer.](https://devblogs.microsoft.com/oldnewthing/20160725-00/?p=93945)" – Joseph Sible-Reinstate Monica Apr 23 '20 at 03:18
  • To my knowledge, only Richedit/Msftedit contains code to do that (ie: you can't do that with you own surface unless you use msftedit to render on your D2D context https://learn.microsoft.com/en-us/windows/win32/api/textserv/nf-textserv-itextservices2-txdrawd2d) but documentation is very very low: https://learn.microsoft.com/en-us/windows/win32/api/tom/nf-tom-itextrange2-buildupmath – Simon Mourier Apr 23 '20 at 06:57
  • 1
    What's stopping you from just evaluating the function? it's as simple as `for (x:range) SetPixel(hdc, x, f(x), color);`. – MSalters Apr 23 '20 at 08:12
  • @MSalters presumably the fact that it's come in similar to `std::string function("f(x) = x + 1");` – Caleth Apr 23 '20 at 11:08

1 Answers1

1

The first step is to parse the string you got from the user. This includes checking for typing errors and providing useful/descriptive error messages (like "Sorry, I don't know what the ^ character means") so the user can know what's wrong and fix their mistake. The result of this should be a set of tokens; where a token is represented by a structure containing an ID (e.g. constant, variable, left bracket, right bracket, add, subtract, multiply, divide, ...) and some data if needed (the value for the constant or the variable name).

The second step is to organize the tokens as a tree; such that operator tokens have children and those children are the values the operator token operates on. This will probably require the use of operator precedence rules (like "BEDMAS" - brackets, exponents, division, multiplication, addition then subtraction) so that "f(x) = x + 1 * 2" is treated like "f(x) = x + (1 *2)" and isn't treated like "f(x) = (x + 1) *2". It will also involve providing useful/descriptive error messages (like "Sorry, you have too many left brackets and not enough right brackets") so the user can know what's wrong and fix their mistake. For example, "f(x) = x * (2 + x) + 1" will become something like:

         [+]
         / \
       [*] [1]
       / \
     [+] [x]
     / \
   [2] [x]

The third step (which is optional in theory) is to optimize the tree. Operators that have constants can be pre-computed (e.g. "f(x) = x * (1 + 2)" can become "f(x) = x * 3"). Addition or subtraction of zero can be discarded (e.g. "f(x) = x * 2 + 0)" can become "f(x) = x * 2"). Multiplication by zero can be discarded (e.g. "f(x) = x + (x * 0)" can become "f(x) = x"). Multiplication or division by one can be discarded (e.g. "f(x) = x + (x * 1)" can become "f(x) = x + x"). Division by zero can either become infinity or become a useful/descriptive error message. Division by a constant can become multiplication by a constant (e.g. "f(x) = x / 4" can become "f(x) = x * 0.25").

The fourth step is to execute the tree somehow. The easiest way would be to interpret the tree yourself. For this; starting with the token at the root of the tree; if the token is a constant return its value, otherwise calculate the value for the child token/s then use the operator token's type to figure out what to do with them and return that value. This is naturally recursive. For high performance, you could convert the tree into native machine code (a JIT compiler).

Note that computers can not do simple mathematical operations correctly. For example, if you use a data type that the computer understands (e.g. double) for something like "((x + 3) / 3 - x) * 100000 - 100000" you will get very wrong results. The problems are rounding (due to lack of precision and/or sometimes needing infinite precision) and overflow. To fix that I'd recommend using rational numbers, where a number is represented as 3 integers in the form "numerator / denominator * 2**exponent" (e.g. so the value 10 would be represented as 5 / 1 * 2**1, and 10/3 would become 5 / 3 * 2**1). With variable sized "big integers" as the integers, this becomes immune to all problems (except for "out of memory", which can only happen if the input string from the user is also extremely huge).

Brendan
  • 35,656
  • 2
  • 39
  • 66