Sign in to follow this  
ajm113

How Would You Write A Dynamic Text Input Calculator?

Recommended Posts

ajm113    355
Hello all, I was wondering how any of you would write a dynamic text input calculator. I.E Lets say you have a single line text input field where the user can type their formula. How would you go about figuring out how to do the correct math calculations from the variables collected in a string?

Lets say the current input field value is "2 + 2"

structure mathStep Vector
enum m_type;
var value;

cLine = removeSpacesInText

For Each Character in cLine Loop

if cLine Character Does Not Equal to any operator.

Add Character to tempString

Else

Convert tempString into correct variable type determining if the string has a period in it.
Then add the variable to the mathStep Vector
After adding it to the to do list then add the operator to the back of the list. Simply by changing the m_type to PLUS and add it to the vector.

End If

End For Loop

If float/double/int use the correct variable type for the result value variable.


For Each Element in mathStep
Add/Subtract/etc to result value
End If

Return Result

I had something like that in mind, I didn't write it in C++ yet, but I've been pondering if there are better ways and variable types to use then adding a bunch of variables in a struct if it's a float or int, a plus, minus, etc in the text we are figuring out what it result is.

Share this post


Link to post
Share on other sites
Dragonion    131
One solution would be to first [url="http://en.wikipedia.org/wiki/Tokenization"]tokenize[/url] the input line using [url="http://en.wikipedia.org/wiki/Regular_expression"]regular expressions[/url]. This would convert the input string "2 + 2" to a token list like { Value(2), Operator(+), Value(2) }. Next, perform a [url="http://en.wikipedia.org/wiki/Parsing"]syntactic analysis[/url] which identifies and organizes (typically in some [url="http://en.wikipedia.org/wiki/Tree_(data_structure)"]tree structure[/url]) the elements that need to be evaluated. Continuing with our "2 + 2" example this would create a tree from the token list with 3 nodes constituting a single addition expression: { Addition(Value(2),Value(2)) }. Lastly, evaluate the tree (or more specifically each node in the tree), which in our example would yield something like Value(4).

Share this post


Link to post
Share on other sites
wforl    169
If you can get your hands one Bjarne's "The C++ Programming Language" book, he explains how to create a calculator. The source code can also be found at his site.

Share this post


Link to post
Share on other sites
Washu    7829
[quote name='Dragonion' timestamp='1333090040' post='4926584']
One solution would be to first [url="http://en.wikipedia.org/wiki/Tokenization"]tokenize[/url] the input line using [url="http://en.wikipedia.org/wiki/Regular_expression"]regular expressions[/url]. This would convert the input string "2 + 2" to a token list like { Value(2), Operator(+), Value(2) }. Next, perform a [url="http://en.wikipedia.org/wiki/Parsing"]syntactic analysis[/url] which identifies and organizes (typically in some [url="http://en.wikipedia.org/wiki/Tree_(data_structure)"]tree structure[/url]) the elements that need to be evaluated. Continuing with our "2 + 2" example this would create a tree from the token list with 3 nodes constituting a single addition expression: { Addition(Value(2),Value(2)) }. Lastly, evaluate the tree (or more specifically each node in the tree), which in our example would yield something like Value(4).
[/quote]
The tree structure you would [url="http://en.wikipedia.org/wiki/Abstract_syntax_tree"]want happens to have a name as well[/url]

Share this post


Link to post
Share on other sites
Dragonion    131
[quote name='Washu' timestamp='1333096964' post='4926606']The tree structure you would [url="http://en.wikipedia.org/wiki/Abstract_syntax_tree"]want happens to have a name as well[/url][/quote]

Thanks, I haven't worked on a compiler since 1998 so I have admittedly forgotten about many of the data structures used in this branch of programming.

Share this post


Link to post
Share on other sites
alvaro    21246
A couple of alternatives that haven't been mentioned:[list]
[*]There is a [url="http://en.wikipedia.org/wiki/Shunting-yard_algorithm"]well-known algorithm[/url] that converts infix notation (what you have) to reverse polish notation. Once you have the expression in RPN, computing the result is trivially achieved using a stack.
[*]You can also write your own [url="http://en.wikipedia.org/wiki/Recursive_descent_parser"]recursive descent parser[/url] for the types of expressions that you expect. I think this is a good exercise to go through at some point.
[/list]

Share this post


Link to post
Share on other sites
laztrezort    1058
I would second alvaro and suggest rolling a recursive descent parser - there are lots of examples and explanations around, and it is indeed a good fundamental excercise.

Share this post


Link to post
Share on other sites
alvaro    21246
Here's a recursive descent parser I just hacked together. The hardest part is reporting meaningful errors, which I haven't been careful about:
[code]#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstdlib>

void skip_white_space(char const *&s) {
while (isspace(*s))
++s;
}

double compute_expression(char const *&s);

double compute_non_signed_factor(char const *&s) {
double result;

if (isdigit(*s)) {
int n_characters_read;
std::sscanf(s, "%lg%n", &result, &n_characters_read);
s += n_characters_read;
skip_white_space(s);
}
else if (*s == '(') {
++s;
skip_white_space(s);
result = compute_expression(s);
if (*s != ')') {
std::cerr << "`)' expected\n";
std::exit(1);
}
++s;
skip_white_space(s);
}
else {
std::cerr << "Number or `(' expected\n";
std::exit(1);
}

return result;
}

double compute_factor(char const *&s) {
bool positive = true;

if (*s == '+')
positive = true, ++s, skip_white_space(s);
else if (*s == '-')
positive = false, ++s, skip_white_space(s);

return positive ? compute_non_signed_factor(s) : -compute_non_signed_factor(s);
}

double compute_term(char const *&s) {
double result = 1.0;
bool dividing = false;

while (1) {
result *= dividing ? 1.0 / compute_factor(s) : compute_factor(s);
if (*s == '*')
dividing = false, ++s, skip_white_space(s);
else if (*s == '/')
dividing = true, ++s, skip_white_space(s);
else break;
}

return result;
}

double compute_expression(char const *&s) {
double result = 0.0;
bool subtracting = false;

while (1) {
result += subtracting ? -compute_term(s) : compute_term(s);
if (*s == '+')
subtracting = false, ++s, skip_white_space(s);
else if (*s == '-')
subtracting = true, ++s, skip_white_space(s);
else break;
}

return result;
}

double compute(char const *s) {
skip_white_space(s);
double result = compute_expression(s);
if (*s != '\0') {
std::cerr << "End of line expected\n";
std::exit(1);
}
return result;
}

int main() {
std::cout << compute("2+2") << '\n';
}

[/code]

EDIT: My code had some issues with unary + and - operators, but I fixed them.

Share this post


Link to post
Share on other sites
Telastyn    3777
I did this as the [url="http://www.assembla.com/wiki/show/TangentParserFramework/Calculator"]example program for my parsing library[/url]

Share this post


Link to post
Share on other sites
Antheus    2409
[quote]how any of you would write a dynamic text input calculator.[/quote]

[code]<script type="text/javascript">
document.write(eval('2+2'));
</script>[/code]

Share this post


Link to post
Share on other sites
alvaro    21246
Telastyn, can that program parse "-(5)" as an expression? I think you might have made the same mistake I initially made and forgot to implement unary operators.

Share this post


Link to post
Share on other sites
alvaro    21246
[quote name='Telastyn' timestamp='1333114377' post='4926674']
Not a mistake, an omission [img]http://public.gamedev.net//public/style_emoticons/default/wink.png[/img]
[/quote]
[img]http://public.gamedev.net//public/style_emoticons/default/biggrin.png[/img]

Share this post


Link to post
Share on other sites
ajm113    355
Thanks for the tips and information guys. I've made my own which works. (Crashes if you have a syntax error. Such as missing right hand operations.) But otherwise it works perfectly fine, I'm still going to fix it up and add more error handling, but if any of you are interested. I used the basic vector list approach instead of binary trees.

I'll have to put your code to the test alvaro and see who's runs better. ;) Mine is more code, but I think it makes it a little more robust.

mathNode.h
[code]

#ifndef MATH_NODE_H
#define MATH_NODE_H

enum MATH_TYPE {
NUMBER = 0,
OPERATOR,
SUB
};


struct mathNode
{
MATH_TYPE m_Type;
double m_dValue;
char m_Op;

std::vector<mathNode> sub;

mathNode()
{
m_Type = SUB;
m_dValue = 0;
m_Op = NULL;
}

mathNode(char op)
{
m_Type = OPERATOR;
m_dValue = 0;
m_Op = op;
sub.reserve(0);
}

mathNode(double m_dValue)
{
m_Type = NUMBER;
m_dValue = m_dValue;
m_Op = NULL;
sub.reserve(0);
}



};


class MathArray
{
public:
MathArray(void);

size_t npos();

void AddElement(double val, size_t i_sub = -1);
void AddElement(char op, size_t i_sub = -1);

size_t AddElementSub();


size_t size();
size_t subs_count();

size_t sub_size(size_t id);


size_t find_first_sub(size_t index = 0);
size_t find_last_sub(size_t index = 0);
size_t find_sub(size_t id);

std::vector<mathNode> getVector();


void clear();

protected:
private:

size_t sub_count;
std::vector<mathNode> root;

};


#endif

[/code]

mathNode.cpp
[code]

#include "stdafx.h"
#include "mathNode.h"


MathArray::MathArray()
{
sub_count = 0;
}

size_t MathArray::npos()
{
return -1;
}


void MathArray::AddElement(char op, size_t i_sub)
{

if(i_sub == npos())
{
mathNode node(op);
root.push_back(node);

return;
}

if(i_sub >= 0 && i_sub < root.size())
{
mathNode node(op);
root.at(i_sub).sub.push_back(node);
}
}


void MathArray::AddElement(double val, size_t i_sub)
{
if(i_sub == npos())
{
mathNode node = mathNode(val);
node.m_dValue = val;
root.push_back(node);

return;
}

if(i_sub >= 0 && i_sub < root.size())
{
mathNode node(val);
node.m_dValue = val;
root.at(i_sub).sub.push_back(node);
}
}

size_t MathArray::AddElementSub()
{
mathNode node;
root.push_back(node);
sub_count++;

return (root.size()-1);
}

void MathArray::clear()
{

sub_count = 0;
for(size_t i = 0; i<root.size(); i++)
{
if(root.at(i).m_Type == SUB)
{
root.at(i).sub.clear();
}
}

root.clear();

}

size_t MathArray::size()
{
return root.size();
}

size_t MathArray::find_first_sub(size_t index)
{

if(index <= npos())
{
index = 0;
}

for(size_t i = index; i<root.size(); i++)
{
if(root.at(i).m_Type == SUB)
{
return i;
}
}

return npos();

}

size_t MathArray::find_last_sub(size_t index)
{
if(index <= npos())
{
index = 0;
}

for(size_t i = index; i>0; i--)
{
if(root.at(i).m_Type == SUB)
{
return i;
}
}

return npos();
}

size_t MathArray::find_sub(size_t id)
{
for(size_t i = 0; i<root.size(); i++)
{
if(root.at(i).m_Type == SUB)
{
return i;
}
}

return npos();
}

size_t MathArray::sub_size(size_t id)
{
if(id < 0 || id >= root.size())
{
return npos();
}

return root.at(id).sub.size();
}

size_t MathArray::subs_count()
{
return sub_count;
}

std::vector<mathNode> MathArray::getVector()
{
return root;
}

[/code]

Calculator.cpp
[code]

#include "StdAfx.h"
#include "Calculator.h"

Calculator::Calculator(void)
{

}


bool Calculator::CanBeUsedInCalculator(std::string line)
{

for(size_t i = 0; i<line.size(); i++)
{

if(line[i] >= 40 && line[i] <= 43 || line[i] == 32)
{
continue;
}

if(line[i] >= 45 && line[i] <= 57)
{
continue;
}

return false;

}


return true;
}

double Calculator::CalculateValue(std::string line)
{

line += ' ';
std::string tempValue = "";
bool AddNumber = false;
bool InBraces = false;
size_t sub_index = m_MathRoot.npos();
for(size_t i = 0; i<line.size(); i++)
{

bool IsMinus = false;
if(line[i] == 45)
{
if(m_MathRoot.getVector().at(m_MathRoot.size()-1).m_Type != OPERATOR)
{
IsMinus = true;
}
}

if(line[i] >= 48 && line[i] <= 57 || line[i] == 46 || (line[i] == 45 && !IsMinus))
{
AddNumber = true;
tempValue += line[i];
continue;
}

if(AddNumber)
{
if(line[i] == ' ' || line[i] == '(' || line[i] == ')' ||
line[i] == '-' || line[i] == '+' || line[i] == '*' || line[i] == '/')
{
AddNumber = false;
double d_val = atof(tempValue.c_str());
m_MathRoot.AddElement(d_val, sub_index);
tempValue = "";
}

}

if(line[i] == '(' && !InBraces)
{
InBraces = true;
sub_index = m_MathRoot.AddElementSub();
continue;
}else if(line[i] == ')' && InBraces){
InBraces = false;
sub_index = m_MathRoot.npos();
}

switch(line[i])
{
case '+':
m_MathRoot.AddElement('+', sub_index);
break;

case '-':
m_MathRoot.AddElement('-', sub_index);
break;

case '*':
m_MathRoot.AddElement('*', sub_index);
break;

case '/':
m_MathRoot.AddElement('/', sub_index);
break;
}

continue;

}

//After compiling, calculate the results!
double result = 0;
double last_result = m_MathRoot.getVector().at(0).m_dValue;

for(size_t i = 1; i<m_MathRoot.size(); i += 2)
{

if(i+1 >= m_MathRoot.size())
{
printf("Syntax Error!\n");
m_MathRoot.clear();
return 0;
}

double sub_result = 0.0;
double sub_last_result = last_result;
if(m_MathRoot.getVector().at(i+1).m_Type == SUB)
{
sub_last_result = m_MathRoot.getVector().at(i+1).sub.at(0).m_dValue;

for(size_t b = 1; b<m_MathRoot.getVector().at(i+1).sub.size(); b += 2)
{
if(b+1 >= m_MathRoot.getVector().at(i+1).sub.size())
{
printf("Syntax Error!\n");
m_MathRoot.clear();
return 0;
}
sub_result = Calculate_Factor(sub_last_result, m_MathRoot.getVector().at(i+1).sub.at(b+1).m_dValue, m_MathRoot.getVector().at(i+1).sub.at(b).m_Op);
sub_last_result = sub_result;
}
}

double right = 0;

if(m_MathRoot.getVector().at(i+1).m_Type == SUB)
{
right = sub_last_result;
}else{
right = m_MathRoot.getVector().at(i+1).m_dValue;
}

result = Calculate_Factor(last_result, right, m_MathRoot.getVector().at(i).m_Op);
last_result = result;
}

//We are done so clean up!
m_MathRoot.clear();

return result;

}

double Calculator::Calculate_Factor(double left, float right, char op)
{

if(op == '+')
{
left += right;
}
else if(op == '-')
{
left -= right;
}
else if(op == '*')
{
left *= right;
}
else if(op == '/')
{
left /= right;
}


return left;
}

[/code]


Example Code:
[code]

if(m_Calculator.CanBeUsedInCalculator(str))
{
double val = m_Calculator.CalculateValue(str);

double intpart;
if(modf (val , &intpart) == 0.0)
{
printf("%i", (int)val);
}else{
printf("%f", val);
}
}
[/code]

Share this post


Link to post
Share on other sites
alvaro    21246
[quote name='ajm113' timestamp='1333340715' post='4927369']
I'll have to put your code to the test alvaro and see who's runs better. ;) Mine is more code, but I think it makes it a little more robust.
[/quote]

I have to take offense to that... Your code crashes when there is a syntax error but you think it's more robust than mine? What part of my code is not robust?

Share this post


Link to post
Share on other sites
ajm113    355
Sorry I don't mean to offense, I was just saying that in sarcasm [img]http://public.gamedev.net//public/style_emoticons/default/tongue.png[/img]. I've fixed up my code not to crash. Btw I've found a bug in your code alvaro. I've attached a comparison when using this argument. "5 - -4 * 3.141". Yours is a bit off. I was going to do a speed test for fun, but I didn't get around to it. I'm guesting yours maybe faster. Since mine goes through a lot of loops and syntax handling.

Share this post


Link to post
Share on other sites
Antheus    2409
5 - -4 * 3.141 = 17.564

How much do you get?


Gotcha:
(5) - ( (-1) * (4) * (3.141) ) = (5) - ( (-1) * (12.564) ) = (5) - ( -12.564 ) = 5 + 12.564 = 17.564


Also:
[code]<html>
<body>
<script>
document.write(eval('5 - -4 * 3.141 '));
</script>
</body>
</html>[/code]

Share this post


Link to post
Share on other sites
ajm113    355
Maybe I'm confusing the process, but when I type this formula say in a Windows calculator I get 28.269 (Which is my code's output), but if I type this in Mac's default calculator it outputs your code's answer of 17.564. Why do I get different results from different calculators. =/ I guest it's not a bug then at all.

Share this post


Link to post
Share on other sites
alvaro    21246
[quote name='ApochPiQ' timestamp='1333393629' post='4927593']
Chill out guys. It's just a calculator.
[/quote]
I write code for a living and take certain pride in the quality of any code I write. He first accused my code of not being robust and then of being buggy. And if the code really has some issues (which is likely), I would like to know what they are so I can avoid them in the future.

But you are right: It's just a calculator. Sorry about taking this so seriously.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this