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;
}