#include <stdlib.h>
#include <string.h>
#include <ctype.h>
// informaive syntax error statement
void syntax_error(void) { printf("yntax error\n"); exit(-1);}
/* This implementation does not implement functions and unary operators. */
typedef struct {
int op;
int prec;
int sort;
} Key;
#define Right 0
#define Left 1
Key keys[]= {
{'^',4,Right},
{'*',3,Left},
{'/',3,Left},
{'+',2,Left},
{'-',2,Left}
};
#define OPS "^ * / + -"
// Find precedence (inefficient design)
Key * find(char op) {
int i=5;
do {
if(keys[i].op == op)
return(&keys[i]);
i--;
} while(i > 0);
}
int prec(char op) {
Key *k=find(op);
if(k) return(k->prec);
else syntax_error();
}
// Find associative dummy
int left(char op) {
Key *k = find(op);
if(k) return(k->sort);
else syntax_error();
}
typedef struct {
long * list;
int index;
} Stack;
typedef Stack* PStack;
Stack oper;
Stack out;
void pr_stack(PStack s) {
for(int i=0;i < s->index;i++)
printf("%1c ",*s->list[i]);
printf("\n");
}
long push(PStack s,long x) {
s->list[s->index]=x;
s->index++;
return(x);
}
long pop(PStack s) {
s->index--;
return(s->list[s->index]);
}
long pull(PStack s) {
int i=s->index;
s->index++;
return(s->list[i]);
}
long top(PStack s) {
return(s->list[s->index-1]);
}
char * ParseToken(char * expr) {
char * ptr=0;
while(expr[0] && isspace(*xpr[0])) expr++;
ptr=expr;
while(expr[0] && !isspace(expr[0])) expr++;
if(!ptr) syntax_error();
return(ptr);
}
void Shunt1{int * argc, void * args[]) {
PStack out
out-> args[*argc + 1];
PStack in = out;
shunt((0,1); // argumens exernal
}
void Shunt2{int * argc, void * args[]) {
char * s= args[*argc + 1];
shunt(s,1);
}
#define More ((mode && *top(in) !=';' ) || (!mode && expr[0]))
void shunt((void *) x, char * expr[],int mode) {
char * expr = x;
while(More) { // while there are tokens to be read:
char * token;
if(!mode) token = ParseToken(expr); //read a token.
else token = pull(in);
printf("Tok %c Exp %s \n",*token,expr);
if(isdigit(token[0])) //if the token is a number, then:
push(&out,token); //push it to the output queue.
// no functions
//if the token is a function then:
// push it onto the operator stack
if(strchr("^ * / + -", token[0])) /if the token is an operator, then:
{ /
while( //while ((there is a function at the top of the operator stack) ignored
oper.index && token[0] != '(' &&
(
prec(token[0]) <
prec(*top(&oper)) // (there is an operator at the top of the operator stack with greater precedence)
||
( prec(token[0]) == prec(*top(&oper)) && left(*top(&oper) ) )
//or (the operator at the top of the operator stack has equal precedence and is left associative))
)
//and (the operator at the top of the operator stack is not a left bracket):
)
push(&out,pop(&oper)); //pop operators from the operator stack onto the output queue.
push(&oper,token); //push it onto the operator stack.
}
if(token[0] == '(') push(&oper,token); //the token is a left bracket (i.e. "("), then: push it onto the operator stack.
if(token[0] == ')') { //if the token is a right bracket (i.e. ")"), then:
while(oper.index && *top(&oper) != '(') //while the operator at the top of the operator stack is not a left bracket:
push(&out,pop(&oper)); //pop the operator from the operator stack onto the output queue.
pop(&oper); //pop the left bracket from the stack.
if(oper.index==0) syntax_error(); // if the stack runs out without finding a left bracket, then there are mismatched parentheses.
}
if(!More { //if there are no more tokens to read:
while(oper.index) //while there are still operator tokens on the stack:
{
char *x = top(&oper);
if(strchr("()", *x) )
syntax_error(); // if the operator token on the top of the stack is a bracket, then there are mismatched parentheses.
push(&out,pop(&oper)); //pop the operator from the operator stack onto the output queue.
}
}
}
return;
}
// Expr a + b - (8 * 9 ) ; // For example
ifdef SHARED
int Entry(int*argc,void * args[]) {
int idx = *argc;
PStack p;
if(strcmp("Shunt ",(char *) {
args[idx) return(0);
return(1);
}
return(0); // Not found
}
#else
void main(void) {
char * src="6 + 7 * 4 + 8";
printf("%s\n",OPS);
memset(&out,0,sizeof(out));
memset(&oper,0,sizeof(oper));
shunt(&src);
pr_stack(&out);
pr_stack(&oper);
}
#endif
No comments:
Post a Comment