I'm writing a program that can soft mathematical equations. The euquations are user specified including +, -, ^, *, /, operations. The program are required to scan the equation from the user and soft it for them. My biggest difficulty is that I don't know how to scan an equation from the user and store it for later use. Can some kind people help me out?! Thanks!
Use a binary tree and presedence rules with each node representing an operation and each leaf representing a value.
thanks for the suggestion. sadly I haven't had any class and experience on data structure. Is there any other simpler approach that avoid the use of using binery tree??
If you're not concerned about operator presedence and about physically storing the expression, then the problem isn't too tough. Just perform the calculations as you read them from the string.
If you understand stacks you can easily make a way of calculating expressions in reverse-polish notation.
Disclaimer : this is all theoretical, I only wrote an expression parser once before and I did it with trees as Polymorphic suggested.
"4/2+3^2"
break it up into 2 arrays:
(doubles)
4.0, 2.0, 3.0, 2.0
and the operators:
(chars)
/ + ^
Then I would go through the operators array and look for the first one with priority ^, * or /, + or -.
Since the operators and numbers were stored in order you can find that 3.0 and 2.0 were associated with the ^ yielding
3.0^2.0
now the arrays look like:
4.0 2.0 9.0
and
/ +
Now you'd determine that / has priority and the equation is 4/2 yielding 2
2.0 and 9.0 with the + operator --> 11.0
Splitting it up into arrays should be pretty easy, and I believe from there you should be able to figure out how to loop through until you have only one number and 0 operators.
Expression trees can get confusing when you bring in precedence. Here's a parser that uses stacks and postfix notation to solve the problem. It's not perfect, I just wrote it up real quick, and it's in C...sorry :-)
Code:#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
enum {integral, op, nesting};
typedef struct {
int token_type;
char token_value[50];
} token;
void remove_ws(char *src)
{
char *p;
char *q;
for (p = q = src; (*p = *q) != '\0'; q++)
{
if (!isspace(*q))
{
p++;
}
}
}
token fill_token(char *start, size_t n)
{
token new_token;
new_token.token_value[0] = '\0';
if (isdigit(*start))
{
new_token.token_type = integral;
}
else if (strspn(start, "()") == 0)
{
new_token.token_type = op;
}
else
{
new_token.token_type = nesting;
}
strncat(new_token.token_value, start, n);
return new_token;
}
int convert(token list[], token new_list[], size_t n_tokens)
{
size_t i;
size_t top;
size_t index;
token t_stack[100];
top = 0;
index = 0;
for (i = 0; i < n_tokens; i++)
{
if (strchr(list[i].token_value, '(') == 0 &&
list[i].token_type == nesting)
{
new_list[index++] = t_stack[--top];
}
else if (list[i].token_type == op)
{
t_stack[top++] = list[i];
}
else if (list[i].token_type == integral)
{
new_list[index++] = list[i];
}
}
return index;
}
int eval(token list[], size_t n_tokens)
{
size_t i;
size_t top;
int i_stack[100];
top = 0;
for (i = 0; i < n_tokens; i++)
{
if (list[i].token_type == op)
{
int a = i_stack[--top];
int b = i_stack[--top];
if (strcmp(list[i].token_value, "+") == 0)
{
i_stack[top++] = b + a;
}
else if (strcmp(list[i].token_value, "-") == 0)
{
i_stack[top++] = b - a;
}
else if (strcmp(list[i].token_value, "*") == 0)
{
i_stack[top++] = b * a;
}
else if (strcmp(list[i].token_value, "/") == 0)
{
if (a > 0)
{
i_stack[top++] = b / a;
}
}
}
else if (list[i].token_type == integral)
{
i_stack[top++] = atoi(list[i].token_value);
}
}
return i_stack[--top];
}
int evaluate(token list[], size_t n_tokens)
{
size_t n;
token new_list[100];
/* Convert to postfix notation */
n = convert(list, new_list, n_tokens);
/* Evaluate the postfix expression */
return eval(new_list, n);
}
int tokenize(char *buff, token token_list[])
{
char *start;
size_t end;
size_t i;
i = 0;
start = buff;
while (*start != '\0')
{
if ((end = strcspn(start, "()/*+-")) == 0)
/* Look for an operand first */
{
if ((end = strspn(start, "/*+-")) == 0)
/* Look for an operator second */
{
/* Look for a nesting last */
end = strspn(start, "()");
}
}
token_list[i++] = fill_token(start, end);
start += end;
}
return i;
}
int main(void)
{
token token_list[100];
char buff[100];
int n;
printf("Enter a fully parenthesized infix expression. Ex. ((4+6)*2)\n");
printf("%% ");
fflush(stdout);
gets(buff);
remove_ws(buff);
n = tokenize(buff, token_list);
printf("%s = %d\n", buff, evaluate(token_list, n));
return 0;
}
i wrote this program along time ago to solve math expressions..hope this helps
Code:#include <iostream> // For stream input/output
#include <cstdlib> // For the exit() function
#include <cctype> // For the isdigit() function
#include <string> // For the strcpy function
using namespace std;
void eatspaces(char* str); // Function to eliminate blanks
double expr(char* str); // Function evaluating an expression
double term(char* str, int& index); // Function analyzing a term
double number(char* str, int& index); // Function to recognize a number
char* extract(char* str, int& index); //Function to extract a substring
const int MAX = 80; // Maximum expression length including '\0'
int main(void)
{
char buffer[MAX] = {0}; // Input area for expression to be evaluated
cout << endl
<< "Welcome to your friendly calculator."
<< endl
<< "Enter an expression, or an empty line to quit."
<< endl;
for(;;)
{
cin.getline(buffer, sizeof buffer); // Read an input line
eatspaces(buffer); // Remove blanks from input
if(!buffer[0]) // Empty line ends calculator
return 0;
cout << "\t= " << expr(buffer) // Output value of expression
<< endl << endl;
}
}
// Function to eliminate blanks from a string
void eatspaces(char* str)
{
int i=0; // 'Copy to' index to string
int j=0; // 'Copy from' index to string
while((*(str+i) = *(str+j++)) != '\0') // Loop while character
// copied is not \0
if(*(str+i) != ' ') // Increment i as long as
i++; // character is not a blank
return;
}
// Function to evaluate an arithmetic expression
double expr(char* str)
{
double value = 0; // Store result here
int index = 0; // Keeps track of current character position
value = term(str, index); // Get first term
for(;;) // Infinite loop, all exits inside
{
switch(*(str+index++)) // Choose action based on current character
{
case '\0': // We're at the end of the string
return value; // so return what we have got
case '+': // + found so add in the
value += term(str, index); // next term
break;
case '-': // - found so subtract
value -= term(str, index); // the next term
break;
default: // If we reach here the string
cout << endl // is junk
<< "Arrrgh!*#!! There's an error"
<< endl;
exit(1);
}
}
}
// Function to get the value of a term
double term(char* str, int& index)
{
double value = 0; // Somewhere to accumulate the result
value = number(str, index); // Get the first number in the term
// Loop as long as we have a good operator
while((*(str+index)=='*')||(*(str+index)=='/'))
{
if(*(str+index)=='*') // If it's multiply,
value *= number(str, ++index); // multiply by next number
if(*(str+index)=='/') // If it's divide,
value /= number(str, ++index); // divide by next number
}
return value; // We've finished, so return what we've got
}
// Function to recognize an expression in parentheses
// or a number in a string
double number(char* str, int& index)
{
double value = 0.0; // Store the resulting value
if(*(str+index) == '(') // Start of parentheses
{
char* psubstr = 0; // Pointer for substring
psubstr = extract(str, ++index); // Extract substring in brackets
value = expr(psubstr); // Get the value of the substring
delete[]psubstr; // Clean up the free store
return value; // Return substring value
}
while(isdigit(*(str+index))) // Loop accumulating leading digits
value=10*value + (*(str+index++) - 48);
// Not a digit when we get to here
if(*(str+index)!='.') // so check for decimal point
return value; // and if not, return value
double factor = 1.0; // Factor for decimal places
while(isdigit(*(str+(++index)))) // Loop as long as we have digits
{
factor *= 0.1; // Decrease factor by factor of 10
value=value + (*(str+index)-48)*factor; // Add decimal place
}
return value; // On loop exit we are done
}
// Function to extract a substring between parentheses
// (requires string)
char* extract(char* str, int& index)
{
char buffer[MAX]; // Temporary space for substring
char* pstr=0; // Pointer to new string for return
int numL = 0; // Count of left parentheses found
int bufindex = index; // Save starting value for index
do
{
buffer[index-bufindex] = *(str+index);
switch(buffer[index-bufindex])
{
case ')':
if(numL==0)
{
buffer[index-bufindex] = '\0'; // Replace ')' with '\0'
++index;
pstr = new char[index-bufindex];
if(!pstr)
{
cout << "Memory allocation failed,"
<< " program terminated.";
exit(1);
}
strcpy(pstr,buffer); // Copy substring to new memory
return pstr; // Return substring in new memory
}
else
numL--; // Reduce count of '(' to be matched
break;
case '(':
numL++; // Increase count of '(' to be matched
break;
}
} while(*(str+index++) != '\0');// Loop - don't overrun end of string
cout << "Ran off the end of the expression, must be bad input."
<< endl;
exit(1);
return pstr;
}