Making an ASCII Graphing Calculator Using C Standard Library
Constructing an ASCII graphing calculator display with a built-in mathematical expression interpreter from scratch in C.
“calculator.c” was born as a scholarship project for the Student Innovation Scholarship. Initially, I decided on writing a simple ASCII display to graph functions, but upon completion of my initial prototype, I realized the problem was far more difficult than I’d initially anticipated. Revisiting the project after a year long break made the fact clear that there was a lot more to this project that meets the eye, so let’s walk through the process that goes into building an ASCII graphing calculator from scratch!
Constructing an ASCII Display
The initial implementation of the calculator starts with an array of pixels that served as the graphing display. Each pixel holds a single character which is what it will display as well as a relative x and y coordinate that is determined by the window boundaries. Initializing the display also requires us to calculate these relative coordinates for each pixel so that we can accurately compute the output of a mathematical function down the line.
// converts indices of pixels in a 2d array from absolute positions to positions relative to the origin on the x - y plane.
pixel **quantify_plane(long double x_steps, long double y_steps, long double xmin, long double ymax) {
pixel **display = initialize_display();
for(int y = 0; y < WINDOW_HEIGHT; y++) {
for(int x = 0; x < WINDOW_WIDTH; x++) {
*&display[y][x].x = (xmin + (x_steps * x));
*&display[y][x].y = (ymax - (y_steps * y));
}
}
return display;
}Here, x_steps and y_steps represent the steps between each pixel given the maximum and minimum display values on each axis relative to the absolute window resolution of the entire display.
// calculates the width and height of each pixel on the (x, y) plane using the boundaries.
long double x_steps = ((xmax-xmin) / WINDOW_WIDTH);
long double y_steps = ((ymax-ymin) / WINDOW_HEIGHT);In order to actually draw a mathematical function though, we need x and y axes to visualize a cartesian plane. To do this, we need a function that draws an empty x-y plane.
// sets the display of every pixel to the correct ascii character.
void draw_plane(pixel **display, long double x_steps, long double y_steps) {
long double rel_x, rel_y, output;
for(int y = 0; y < WINDOW_HEIGHT; y++) {
for(int x = 0; x < WINDOW_WIDTH; x++) {
pixel *pixel = &display[y][x];
rel_x = pixel -> x;
rel_y = pixel -> y;
bool x_zero = close_to(rel_x, 0, x_steps/2.1);
bool y_zero = close_to(rel_y, 0, y_steps/2.1);
bool origin = x_zero && y_zero;
if(origin)
pixel -> display = '+';
else if(x_zero)
pixel -> display = '|';
else if(y_zero)
pixel -> display = '-';
else
pixel -> display = ' ';
}
}
}The close_to function solves a fundamental problem with using an ASCII display, which is that each pixel is an approximation of the values that are contained within a region rather than being exact points on a plane. Because of this, we need to approximate when a value falls within a pixel so that we can shade that pixel to appropriately represent the output of a mathematical function.
Drawing Functions
After initializing an empty display, we can now approach graphing a mathematical function on it.
Fortunately, this is easy, all we have to do is shade a pixel when it represents the output of a given method at its own relative x coordinate. To do this, we can use a similar function to draw_plane
// sets the display of the pixel to # if it approximates a functions output
void draw_line(pixel **display, long double x_steps, long double y_steps) {
long double rel_x, rel_y, output;
for(int y = 0 ; y < WINDOW_HEIGHT ; y++) {
for(int x = 0 ; x < WINDOW_WIDTH ; x++) {
pixel *pixel = &display[y][x];
rel_x = pixel -> x;
rel_y = pixel -> y;
output = function(rel_x);
if(close_to(output, rel_y, y_steps/2.1))
pixel -> display = '#';
}
}
}Let’s try running the code we have so far using the function x^2 .
So the good news is that our code works! The bad news makes itself immediately clear past a cursory observation. The graph looks horrible. To fix it, we need to look at the source of the issue. Right now, we are setting the display of each pixel to a hashtag as long as it approximates the output of the mathematical function, but what if there was a better way to visually approximate the output within each individual pixel?
Welcome to the World of ASCII Art!
When looking at ASCII art, it becomes clear that there’s a lot more we can do with character displays than just using a hashtag for everything. Although we can’t expect to reach the level of human ASCII artists with a simple algorithm, we can use ASCII art techniques to improve our existing display by a wide margin.
In order to get the biggest bang for our buck, we need to focus on where our display is the most deficient in terms of visual precision. Character slots on a monospace terminal font are taller than they are wide, so we need a way to artificially inflate the vertical resolution of our display. To do this, we need to define the characters that we want to use.
If we take a look at the character '.' and '-' side by side, one is slightly higher than the other. We can use this concept to construct an ASCII palette that represents a more gradual change in y value. For this palette, the calculator uses "_,.-~*'`" , which is a useful palette both because it can be globally displayed on any terminal, and because it is exactly what we need in terms of a gradual transition between y values.
To implement an artificially inflated vertical resolution, we need to use a function that approximates the y value of an input within a pixel. The code would look something like this:
// returns a different ascii character based on how close a value is to the end of a range of values.
char ycompress(long double num, long double pixel, long double range) {
char *table = "_,.-~*'`";
// splits the pixel's height by 1/8
long double steps = range/8;
long double goal = num - (pixel - (range/2) );
int counter = 0;
long double step = 0;
while(step < goal) {
step += steps;
counter++;
}
return table[counter - 1];
}After implementing a higher vertical resolution, the results speak for themselves. Here is the same function x^2 graphed with the new system:
Not only does this fix the visual accuracy problem, but it also has the added bonus of that ASCII charm that this program was inspired by in the first place!
In its current state, the calculator is running its graphing algorithm on a preset function function that takes an x value and returns a y value, however, what if we wanted to make the calculator user friendly? Turns out this problem is a lot easier said than done. In order to take input from the user we need to parse mathematical expressions, a task that more than doubles the work we have to do.
Interpereting Mathematical Expressions
To illustrate this problem, let’s use the mathematical expression x^(2x+4) as an example. At a glance, it’s very easy for humans to evaluate this expression given a substitute for x, but it’s a completely different story for computers. In order for a computer to properly evaluate a mathematical expression that is written for humans, some preprocessing must be performed. The most common approach to doing this is to distill the mathematical expression into a format that is easily digestible by a computer. One of these formats is called Reverse Polish Notation (RPN), or more simply, postfix notation.
Before defining postfix notation, we need to take a closer look at the way people write expressions. For x^(2x+4) for instance, we can see that the operands of the expression (ie. the numbers and variables) are placed on either side of their operator. For this reason, the way that people write mathematical expressions is referred to as infix notation. In contrast, postfix notation is when the operators are written after the operands. After applying this rule to our example, x^(2x+4) becomes x2x*4+^ . Here we can see two major differences between postfix and infix notation that I have not mentioned yet. First, implied multiplication operations are explicitly written, for instance 2x becomes 2x* , which eliminates about a dozen edge cases when actually evaluating the expression using an algorithm later on. Second, after converting to postfix notation there is no longer any need for parentheses, because of its inherent left-to-right evaluation order. Both of these differences become huge performance improvements when it comes to algorithmically evaluating postfix notation for every function input later down the line.
String Tokenization
The process of actually converting to postfix notation requires us to identify operands from operators and properly parse parentheses in the context of the equation as a whole. This is referred to as tokenization. Tokenizing a string can be done in many ways, but the way that we will approach the problem is through the use of a state machine. Essentially, the current state of the parser is determined by what the current character is identified as, and a different string tokenization process is taken depending on what the current character is.
Before we tackle tokenization, however, we need to do some preprocessing to make the expression more algorithmically digestible. To do this, we need a structure that stores all of the current parser data. Here is the definition of this structure:
// current parser data.
typedef struct {
char *input;
int pos;
int token_pos;
int token_cnt;
char **tokens;
p_type *types;
p_state state;
char *mkstr;
} p_data;Here, we have the initial mathematical expression stored as the input, along with some increment variables to store the progress of the tokenization process. The structures p_type and p_state are enumerations that represent the type of the current token and the current state of the parser respectively, this will help us when evaluating the output and logging errors. Finally, we define a mkstr (functionally the same as a makefile for C) that will store the output of our preprocessed mathematical expression.
Now we can start constructing our mkstr by preprocessing and simplifying our input . We can do this in two major steps that will set us up to properly tokenize the makestring later on:
- Replace all explicit mathematical functions with one character that identifies them (e.g. insert an
sinstead ofsin, anSforcsc, anlinstead oflog, etc.) - Insert multiplication symbols where implied (e.g.
2*xinstead of2xand for parentheses2*(4)instead of2(4)).
Here is the implementation of these two steps in C code:
// preprocessing done to input in order to produce a makestring.
void preprocess(p_data *data) {
int length = strlen(data -> input);
data -> mkstr = (char *) calloc(length * 2, sizeof(char));
// encodes trig functions.
char *b_string = (char *) calloc(length, sizeof(char));
for(int i = 0, j = 0; j < length; i++, j++) {
if(isin(data -> input[j], "sctl")) {
if(encode_trig(data -> input + j) != '\0') {
b_string[i] = encode_trig(data -> input + j);
j+=2;
} else data -> state = STATE_err;
} else b_string[i] = data -> input[j];
}
// insert multiplication symbol where implied by mathematical notation: 2x, xsinx, 3(2-1), etc...
for(int i = 0, j = 0; i < strlen(b_string); i++, j++) {
if((isin(b_string[i+1], "sScCtTl" ) && !isin(b_string[i] , "sScCtTl({[/+-*^" ))
|| (isin(b_string[i+1], "([{" ) && !isin(b_string[i] , "([{sScCtTl/+-*^" ))
|| (isin(b_string[i] , ")}]" ) && isin(b_string[i+1], "([{xpesScCtTl1234567890"))
|| (isin(b_string[i] , "0123456789." ) && isin(b_string[i+1], "([{xsScCtTlpe" ))
|| (isin(b_string[i] , "xpe" ) && isin(b_string[i+1], "0123456789sScCtTl([{x" ))) {
data -> mkstr[j] = b_string[i]; j++;
data -> mkstr[j] = '*';
} else { data -> mkstr[j] = b_string[i]; }
} free(b_string);
}Here we had to manually compute where a multiplication symbol was implied for every edge case that modern mathematical convention includes.
Now that we have a precompiled mkstr we can approach tokenizing it. The general process for tokenization that we’re going to take is going to involve looking at the input string character by character and identifying it based on type. To identify it, we can use a function that simply checks what type the current character is and returns a p_state corresponding to that type. This is also known as a state machine.
// returns the current state of the parser based on the type of the character that is being parsed.
p_state identify(char c) {
if(isin(c, function_shorthand)) return STATE_trg;
else if(isin(c, "^+/*-")) return STATE_opr;
else if(isin(c, "pe")) return STATE_con;
else if(isin(c, "()[]{}")) return STATE_par;
else if(c == 'x') return STATE_var;
else if((c >= '0' && c <= '9') || c == '.') return STATE_num;
else if(c == '\0' || c == '\n') return STATE_end;
return STATE_err;
}Notice that the use of a state machine provides us with easy error checking and handling.
We can use this method to loop through every character in our input string and break up the current token based on a different set of rules for each type of character. Crucially, as we loop through the characters in the input , we will store the type of the token as a p_type in the types array. This will help us when we are reordering and evaluating the string later on down the line.
// converts string input into tokenized input.
void tokenize(p_data *data) {
if(data -> state == STATE_err) {
throw_error("invalid token");
} data -> state = STATE_str;
// state machine loop until end or error encountered.
char *curstr = data -> mkstr;
while(data -> state != STATE_err && data -> state != STATE_end) {
switch(data -> state) {
// STATE_str is the default state, during which the next character's token is identified.
case STATE_str:
data -> state = identify(curstr[0]); break;
// findnum is called in the case of a number.
case STATE_num:
data -> types[data -> token_pos] = TYPE_num;
findnum(data, curstr);
data -> state = STATE_str; break;
// parentheses are treated as single-character tokens.
case STATE_par:
data -> types[data -> token_pos] = TYPE_par;
add_ctoken(data, curstr[0]);
data -> state = STATE_str; break;
// variables are treated as single-character tokens.
case STATE_var:
data -> types[data -> token_pos] = TYPE_var;
add_ctoken(data, curstr[0]);
data -> state = STATE_str; break;
// if it is a constant then it is treated like a number.
case STATE_con:
data -> types[data -> token_pos] = TYPE_con;
add_ctoken(data, curstr[0]);
if(curstr[0] == 'p') data -> pos++;
data -> state = STATE_str; break;
// trig functions are treated as single-character tokens.
case STATE_trg:
data -> types[data -> token_pos] = TYPE_trg;
add_ctoken(data, curstr[0]);
data -> state = STATE_str; break;
// operations are treated as single-character tokens.
case STATE_opr:
// if the operation is a negative, then it could potentially be the start of a negative number and not part of an operation.
if(curstr[0] == '-' && (data -> pos == 0 || !isin(data -> mkstr[ + data -> pos - 1], "1234567890)]}xpe"))) {
// this is handled by adding a zero token to the token array and then treating the negative as an operator.
data -> types[data -> token_pos] = TYPE_num;
add_ctoken(data, '0');
data -> pos--;
data -> types[data -> token_pos] = TYPE_opr;
add_ctoken(data, curstr[0]);
data -> state = STATE_str;
} else {
data -> types[data -> token_pos] = TYPE_opr;
add_ctoken(data, curstr[0]);
data -> state = STATE_str;
} break;
case STATE_end: return; break;
case STATE_err: return; break;
}
curstr = data -> mkstr + data -> pos;
}
}Now that we’ve successfully tokenized the string input , we can finally write an algorithm that orders the string array in postfix notation!
Converting to Postfix Notation
To solve the issue of converting to postfix notation, we need to approach the tokenized string algorithmically. The traditional way of doing this is through something known as the shunting yard algorithm. The process is as follows:
Loop through the tokenized string:
- If the current token is an operand, push it to the output.
- If the current token is an operator:
– If the operator that is at the top of the stack comes later than the current token in the order of operations, push the top of the stack to the output.
– Otherwise, push the current token to the top of the stack. - If the current token is an open parenthesis, push it to the stack.
- If the current token is a close parenthesis, push the top of the stack to the output until an open parenthesis is reached.
Here is the implementation of this algorithm in C
// converts the tokens from infix notation (x+2, 2x^3, sin(cos(x)), etc..) to postfix notation (x2+, 2x3^*, xcs, etc...).
void infix_to_postfix(p_data *data) {
int length = strlen(data -> mkstr);
char **output = (char **) calloc(length, sizeof(char*));
char **stack = (char **) calloc(length, sizeof(char*));
int top = 0, output_position = 0, pcount = 0;
if(data -> state == STATE_err) {
throw_error("invalid token");
} data -> state = STATE_str;
// loops to the end of token array.
for( ; data -> token_pos < data -> token_cnt ; data -> token_pos++) {
switch(data -> types[data -> token_pos]) {
// numbers are appended immediately to the output.
case TYPE_num:
output[output_position] = data -> tokens[data -> token_pos];
output_position++;
break;
// operations are appended to the stack in order of priority.
case TYPE_opr:
if(!(stack[top])) {
stack[top] = data -> tokens[data -> token_pos];
} else if(isin(stack[top][0], "[{(")) {
top++;
stack[top] = data -> tokens[data -> token_pos];
} else if(operation_order(data -> tokens[data -> token_pos][0]) > operation_order(stack[top][0])) {
output[output_position] = stack[top];
stack[top] = data -> tokens[data -> token_pos];
output_position++;
} else {
top++;
stack[top] = data -> tokens[data -> token_pos];
}
break;
// variables are treated as numbers.
case TYPE_var:
output[output_position] = data -> tokens[data -> token_pos];
output_position++;
break;
case TYPE_con:
output[output_position] = data -> tokens[data -> token_pos];
output_position++;
break;
// open parentheses are added to the stack, close parentheses initiate a loop that adds to the output until the open parentheses is found.
case TYPE_par:
if(isin(data -> tokens[data -> token_pos][0], "[{(")) {
if(stack[top])
top++;
stack[top] = data -> tokens[data -> token_pos];
} else {
while(!isin(stack[top][0], "[{(")) {
output[output_position] = stack[top];
top--;
output_position++;
}
top--;
if(top >= 0 && isin(stack[top][0], "sScCtTl")) {
output[output_position] = stack[top];
top--;
output_position++;
}
} pcount++;
break;
// trig functions are appended to the stack, and effectively treated as operations until the expression is evaluated.
case TYPE_trg:
top++;
stack[top] = data -> tokens[data -> token_pos];
break;
}
}
// adds whatever operations are in the stack to the output.
while(top > -1) {
output[output_position] = stack[top];
top--;
output_position++;
}
data -> tokens = output;
data -> token_cnt -= pcount;
data -> token_pos = 0;
}Here we can see that the major structure of infix_to_postfix follows a similar pattern as the tokenize function, with the crucial difference being that instead of the cases corresponding to the state of the parser, they correspond to the p_type of the current index in the types array. This not only saves us time during this pass, but also later on when we need to evaluate the output of the mathematical expression.
Compiling and Evaluating
Now that we have all the tools necessary to compile our makestring, we just need to assemble them into one function that we can call once for every new expression we come across as user input.
void compile(p_data *data) {
preprocess(data);
data -> tokens = (char **) calloc(MAX_COMPLEXITY, sizeof(char *));
data -> types = (p_type *) calloc(MAX_COMPLEXITY, sizeof(p_type));
data -> pos = 0;
data -> token_pos = 0;
tokenize(data);
data -> token_cnt = data -> token_pos;
data -> pos = 0;
data -> token_pos = 0;
infix_to_postfix(data);
}And we’ve done it! We have officially completed the necessary steps before actually evaluating the output of the initial mathematical expression. Luckily, this step is much simpler since we properly set ourselves up with all the resources we need for evaluation. Now that the tokens array is in postfix order, we can use a stack in conjunction with a loop to evaluate each operation individually moving from left to right.
// evaluates the postfix string.
long double evaluate(long double xvalue, p_data *data, long double base) {
long double *stack = calloc(data -> token_cnt, sizeof(long double));
bool *states = calloc(data -> token_cnt, sizeof(bool));
int top = 0;
// loops through until the end of the token array.
for( ; data -> token_pos < data -> token_cnt ; data -> token_pos++) {
// if it is an operand, it gets pushed to the stack.
if(isin(data -> tokens[data -> token_pos][0], "1234567890.xpe")) {
if(states[top])
top++;
// x is substituted for the x value and pushed to the stack.
if(data -> tokens[data -> token_pos][0] == 'x') {
stack[top] = xvalue;
states[top] = true;
} else if(data -> tokens[data -> token_pos][0] == 'p') {
stack[top] = atan(1) * 4;
states[top] = true;
} else if(data -> tokens[data -> token_pos][0] == 'e') {
stack[top] = exp(1);
states[top] = true;
} else {
stack[top] = atof(data -> tokens[data -> token_pos]);
states[top] = true;
}
} else if(isin(data -> tokens[data -> token_pos][0], "+-/^*sScCtTl")) {
// if it is an operator, the operator is carried out with the top two items of the stack.
switch(data -> tokens[data -> token_pos][0]) {
case '+':
if(top-1 < 0)
throw_error("invalid operation");
long double sum = stack[top] + stack[top-1];
top--;
stack[top] = sum;
break;
case '-':
if(top-1 < 0)
throw_error("invalid operation");
long double difference = stack[top-1] - stack[top];
top--;
stack[top] = difference;
break;
case '*':
if(top-1 < 0)
throw_error("invalid operation");
long double product = stack[top] * stack[top-1];
top--;
stack[top] = product;
break;
case '/':
if(top-1 < 0)
throw_error("invalid operation");
long double quotient = stack[top-1] / stack[top];
top--;
stack[top] = quotient;
break;
case '^':
if(top-1 < 0)
throw_error("invalid operation");
long double result = (long double) pow(stack[top-1], stack[top]);
top--;
stack[top] = result;
break;
// if it is a trig function, it is treated like an operator and is performed on the top item of the stack.
case 's':
if(!states[top])
throw_error("invalid sin");
stack[top] = (long double) sin(stack[top]);
break;
case 'S':
if(!states[top])
throw_error("invalid csc");
stack[top] = (long double) (1/sin(stack[top]));
break;
case 'c':
if(!states[top])
throw_error("invalid cos");
stack[top] = (long double) cos(stack[top]);
break;
case 'C':
if(!states[top])
throw_error("invalid sec");
stack[top] = (long double) (1 / cos(stack[top]));
break;
case 't':
if(!states[top])
throw_error("invalid tan");
stack[top] = (long double) tan(stack[top]);
break;
case 'T':
if(!states[top])
throw_error("invalid cot");
stack[top] = (long double) (1 / tan(stack[top]));
break;
case 'l':
if(!states[top])
throw_error("invalid log");
stack[top] = (long double) (log(stack[top])/log(base));
break;
}
} else {
throw_error("syntax");
}
}
data -> token_pos = 0;
return stack[top];
}After all that parsing, we finally have a working calculator! All we have to do is accept user input, store it as the input string to a p_data structure, and…
We can also easily adapt this to fit the interface of a traditional graphing calculator through terminal commands. We can create a function table to graph user input and store them by writing them to a file and loading them in when the program is run, and we can do the same for window boundaries. This makes our calculator behave a lot closer to an actual graphing calculator!
We’re not done yet, though. Our initial goal was to make a graphing calculator, and although we did that, we’re missing one thing that would tie everything together really nicely.
Incorporating Calculus Functionality
This is where it gets a little shaky, because aside from external calculus libraries, trying to develop perfectly accurate calculus functionality from scratch is a nightmare almost as big as the one we just faced. So when it comes to calculus it’s probably better for us to exercise moderation; let’s choose to include derivatives and integrals as our calculator’s calculus suite.
How do we do this? Well, we can adapt the formal definitions of a derivative and an integral using a very small delta value to achieve as accurate of an approximation as we need for this application.
// returns the derivative based on the delta x limit definition of a derivative.
long double derive(long double x_value, p_data *data, long double b) {
return (evaluate(x_value + DELTA, data, base) - evaluate(x_value, data, b)) / DELTA;
}And for integrals…
// returns the definite integral based on given bounds and the delta x summation definition of an integral.
long double integrate(long double left_bound, long double right_bound, p_data *function) {
long double x_value = left_bound;
long double def_int = 0;
long double steps = (right_bound - left_bound) * .00001;
while(x_value < right_bound) {
def_int += evaluate(x_value, function, base) * steps;
x_value += steps;
}
return def_int;
}It’s crucial to mention that this method of implementing integration is slightly innacurate. A better way to approach this would be to dynamically change the size of the steps dynamically within the loop with a better implementation of floating point operations. However, because this is the approach that I initially took when making the project, this will remain as the implementation of integration until the project is improved in the future.
Despite the inaccuracies, after incorporating these functions into our calculator’s command suite, we still get to sit back and enjoy the beauty of our ASCII calculus machine.
To represent a shaded area for integration, we can use a hashtag to represent an area within the boundaries of integration.
Finishing Touches & Limitations
All we need now are quality of life additions such as a /help command, along with the ability to change log() bases and the ability to use and set the x variable in general calculations. After that we’ve finally finished!
There’s one last thing that we need to address, because the program may be functional, but it’s not perfect! There are four major limitations to this calculator:
- The largest limitation by far is floating point imprecision. This can be apparent when it comes to complex expressions in the general calculator functionality, but is most present when it comes to the integration functionality. The computed area under the curve will always be slightly inaccurate, although it will be very close to the actual answer. This was largely minimized through the use of
long doubleinstead offloatordouble, but it unfortunately cannot be completely counteracted. - There are inherent limitations when it comes to the use of ASCII as the display method. While this was intentionally done to stylize the calculator, it still makes it so that the terminal must be at least as wide as the width of the graphing display. The default graphing display. The default graphing display width is 200 characters, so as long as the font size of the terminal is small enough such that it can fit 200 characters in a row, there will be no problem.
- There is one edge case in the parser that has eluded every debugging effort. For some unholy reason, the entire parser breaks if an expression starts with something in parentheses and is followed by anything. like
(x)2,(23)x, or(23)+x. - There is a very rudimentary error-handling system in place, however, this does not cover the integration between outputs that don’t exist. So if, for instance, you are integrating under
log(x), inputting a lower bound of anything less than or equal to 0 will end the program with a segmentation fault, this is because it is impossible to integrate between 0 and anything underlog(x). This also applies to functions with holes and other functions with vertical asymptotes.
Although perhaps the largest limitation of all of this is that there is almost no practical applications for what we’ve created other than flexing your algorithmic muscles and showing off how beautiful ASCII art can be.
All code for this project including a download and instructions for use can be found on my github.