#ifndef _EXPR_H_
#define _EXPR_H_

typedef enum {
STATE_DIGIT, // digits
STATE_OPERATOR, // operators
STATE_RPAREN, // symbolic ')'
STATE_BLANK, // space and tab
STATE_DELIMITER, // symbolic '|'
STATE_UNKNOWN // unrecognized symbolic
} state_e;

typedef enum {
NTYPE_VALUE,
NTYPE_OP
} ntype_e;

typedef struct tagSyntaxTreeNode {
ntype_e t; // node type
union {
char op; // operator;
float value; // value contain in this node
} u;
struct tagSyntaxTreeNode *lchild;
struct tagSyntaxTreeNode *rchild;
} ATTR_SYNTAX_TREE_NODE;

int mid2pos( char mid_e[], char pos_e[] );
float calc_expr( char mid_e[] );
float calc_expr2( ATTR_SYNTAX_TREE_NODE *p_root );

ATTR_SYNTAX_TREE_NODE *create_syntax_tree( char pos_e[] );

void delete_syntax_tree( ATTR_SYNTAX_TREE_NODE *p_root );

#endif

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "expr.h"

static int prio( char op )
{
switch( op )
{
case '+' : case '-': return 1;
case '*' : case '/': return 2;
case '(' : return -1;
default:
return -1;
}
}

static int isop( char op )
{
switch( op )
{
case '+':
case '-':
case '*':
case '/':
case '(':
return 0;
default:
return 1;
}
}

static int isdigit( char c )
{
if( c >= '0' && c <= '9' )
return 0;
return 1;
}

static float calc( float opr1, float opr2, char op )
{
switch( op )
{
case '+': return opr1+opr2;
case '-': return opr1-opr2;
case '*': return opr1*opr2;
case '/': assert(opr2); return opr1/opr2;
}
}

int mid2pos( char mid_e[], char pos_e[] )
{
char op_stack[80];

int top = -1;
int i = 0, j = 0;

state_e s = STATE_UNKNOWN;

while( mid_e[i] != '\0' )
{
if( !isdigit(mid_e[i]) )
s = STATE_DIGIT;
else if( !isop(mid_e[i]) )
{
if( s == STATE_DIGIT )
pos_e[j++] = '|';
else if( s == STATE_OPERATOR && mid_e[i] != '(' )
{
printf("Unrecoginzed operator %c%c\n", mid_e[i-1], mid_e[i]);
return 1;
}
s = STATE_OPERATOR;
}
else if( mid_e[i] == ')' )
s = STATE_RPAREN;
else if( mid_e[i] == 0x20 || mid_e[i] == '\t' )
s = STATE_BLANK;
else
s = STATE_UNKNOWN;

switch( s )
{
case STATE_DIGIT:
while( mid_e[i] != '\0' && !isdigit(mid_e[i]) )
pos_e[j++] = mid_e[i++];
break;
case STATE_OPERATOR:
if( prio(mid_e[i]) > prio(op_stack[top]) || mid_e[i] == '(' )
op_stack[++top] = mid_e[i++];
else
{
while( mid_e[i] != '\0' && prio(mid_e[i]) <= prio(op_stack[top]) )
pos_e[j++] = op_stack[top--];
op_stack[++top] = mid_e[i++];
}
break;
case STATE_RPAREN:
while( top >= 0 && op_stack[top] != '(' )
pos_e[j++] = op_stack[top--];
if( op_stack[top] != '(' )
{
printf("Miss \'(\'\n");
return 1;
}
top--;
i++;
break;
case STATE_BLANK:
i++;
break;
default:
printf("Unrecognized symbolic \'%c\'\n", mid_e[i]);
return 1;
}
}
while( top != -1 )
{
if( op_stack[top] == '(' )
{
printf("Miss \')\'\n");
return 1;
}
pos_e[j++] = op_stack[top--];
}
pos_e[j] = '\0';
return 0;
}

float calc_expr( char pos_e[] )
{
int i = 0, j;
float opr1, opr2;
float opr_stack[80];
int top = -1;

char buf[10];

state_e s = STATE_UNKNOWN;

while( pos_e[i] != '\0' )
{
if( !isdigit(pos_e[i]) )
s = STATE_DIGIT;
else if( !isop(pos_e[i]) )
s = STATE_OPERATOR;
else if( pos_e[i] == '|' )
s = STATE_DELIMITER;
else
s = STATE_UNKNOWN;
switch( s )
{
case STATE_DIGIT:
j = 0;
while( pos_e[i] != '\0' && !isdigit(pos_e[i]) )
buf[j++] = pos_e[i++];
buf[j] = '\0';
opr_stack[++top] = atof(buf);
break;
case STATE_OPERATOR:
opr2 = opr_stack[top--];
opr1 = opr_stack[top];
opr_stack[top] = calc(opr1, opr2, pos_e[i++]);
break;
case STATE_DELIMITER:
i++;
break;
default:
printf("DFA state is unknown!\n");
return -1;
}
}
return opr_stack[top];
}

ATTR_SYNTAX_TREE_NODE *create_syntax_tree( char pos_e[] )
{
int i = 0, j;
int top = -1;

ATTR_SYNTAX_TREE_NODE *p_stack[80];
ATTR_SYNTAX_TREE_NODE *p;

char buf[80];

state_e s = STATE_UNKNOWN;

memset( p_stack, 0, sizeof(ATTR_SYNTAX_TREE_NODE *) * 80);

while( pos_e[i] != '\0' )
{
if( !isdigit(pos_e[i]) )
s = STATE_DIGIT;
else if( !isop(pos_e[i]) )
s = STATE_OPERATOR;
else if( pos_e[i] == '|' )
s = STATE_DELIMITER;
else
s = STATE_UNKNOWN;
switch( s )
{
case STATE_DIGIT:
j = 0;
while( pos_e[i] != '\0' && !isdigit( pos_e[i] ) )
buf[j++] = pos_e[i++];
buf[j] = '\0';
p = (ATTR_SYNTAX_TREE_NODE *)malloc(sizeof(ATTR_SYNTAX_TREE_NODE));
assert(p);
p->t = NTYPE_VALUE;
p->lchild = NULL;
p->rchild = NULL;
p->u.value = (float)atof(buf);
p_stack[++top] = p;
break;
case STATE_OPERATOR:
p = (ATTR_SYNTAX_TREE_NODE *)malloc(sizeof(ATTR_SYNTAX_TREE_NODE));
assert(p);
p->t = NTYPE_OP;
p->u.op = pos_e[i++];
// merge sub-tree
p->rchild = p_stack[top--];
p->lchild = p_stack[top];
p_stack[top] = p;
break;
case STATE_DELIMITER:
i++;
break;
default:
printf("DFA state is unknown!\n");
return NULL;
}
}
return p_stack[top];
}

float calc_expr2( ATTR_SYNTAX_TREE_NODE *p_root )
{
float lvalue, rvalue;

if( p_root->lchild->t == NTYPE_OP )
lvalue = calc_expr2( p_root->lchild );
else
lvalue = p_root->lchild->u.value;

if( p_root->rchild->t == NTYPE_OP )
rvalue = calc_expr2( p_root->rchild );
else
rvalue = p_root->rchild->u.value;

return calc(lvalue, rvalue, p_root->u.op);

}

void delete_syntax_tree( ATTR_SYNTAX_TREE_NODE *p_root )
{
if( p_root != NULL )
{
delete_syntax_tree( p_root->lchild );
delete_syntax_tree( p_root->rchild );
free( p_root );
}
}

#include <stdio.h>
#include <conio.h>

#include "expr.h"

int main()
{
char mid_e[80], pos_e[80];
float result;

ATTR_SYNTAX_TREE_NODE *p_root;

gets(mid_e);
if( !mid2pos(mid_e,pos_e) )
{
p_root = create_syntax_tree(pos_e);
result = calc_expr2(p_root);
printf("= %.1f\n", result);
delete_syntax_tree( p_root );
}
getch();
return 0;
}