PHP Code:
#include<stdlib.h>
#include<string.h>
#include<stdio.h>
#include<math.h>
#define LEN 100
/* Enumerated Data type to determine whether we are in process of getting a number or decimal or new operand/operator */
enum State {OUT, IN, DECIMAL};
enum Sign {POSITIVE, NEGATIVE};
/************************************************LIFO Data Structure using Linked Lists********************************/
typedef struct Node {
double num;
struct Node *ptr;
} Node;
typedef struct Stack {
Node *top;
} Stack;
/* Initialize a stack to NULL */
void Stack_Initialize(Stack *s) {
s->top = NULL;
}
/* Push an element on to a stack. No need to check for bounds, as the nodes are dynamically created */
void Stack_Push(Stack *s, double n) {
/* Create a new node to store the new value */
Node *prevtop = s->top;
Node *newnode;
newnode = (Node*)malloc(sizeof(Node));
newnode->num = n;
newnode->ptr = prevtop; /* Point the pointer in the node to the current top of the stack */
s->top = newnode; /* Point the top of the stack to the new node */
}
/* Pop an element from stack and store it in retnum, if successful return 1, if not return 0 */
int Stack_Pop(Stack *s, double *retnum) {
Node *p = s->top;
/* If the stack top is NULL, that means no data is there in the stack*/
if(s->top == NULL) {
return 0; /* Failure to Pop */
}
*retnum = p->num; /* Store the number on top node of srack in retnum */
s->top = p->ptr; /* Now set the new stack top the stack to the node below the top */
free(p); /* Clean up the top node */
return 1; /* Successful */
}
/************************************************End of Data Structure********************************/
/* Safely get a string, and put space in the end of the input string as sentinel element */
void get_string(char str[])
{
char *newline;
fgets(str, LEN, stdin);
newline = strchr(str, '\n');
*newline = ' ';
}
/* Compute the postfix expression string */
void compute(char postinp[]) {
int i;
double num; /* Variable for storing the extracted decimal number */
char ch; /* Variable to store each character */
int len; /* Length of the string */
enum State n = OUT; /* Set initial state of whether reading a decimal or not as OUT */
enum Sign sign = POSITIVE;
int count_decplaces = 0; /* Variable to determine number of decimal places, in case of . is detected in string for floating point numbers parsing */
Stack pfstack; /* Stack to store operands for postfix evaluation */
double op1, op2, res; /* Variables to hold the operands which are popped out and res is the result stored which is pushed to the stack */
int count_operands = 0; /* Count number of operands, if zero then output nothing */
Stack_Initialize(&pfstack);
len = strlen(postinp);
for(i=0; i<len; ++i) {
ch = postinp[i];
/* Detect use of - as a negative sign */
if(postinp[i]=='-' && (postinp[i+1] >= '0' && postinp[i+1] <= '9') && sign == POSITIVE && n==OUT) {
sign = NEGATIVE;
continue;
}
/* If the character is a numeric type, put it into the current or set as new number */
if((ch>='0' && ch<='9')) {
/* If it's a new number in case n is OUT, and not IN or DECIMAL; set the number's first digit place */
if(n==OUT) {
num = (int)ch-(int)'0';
n=IN;
}
/* If in process of reading a number, multiply the current number by 10 and add the new digit */
/* eg. if we read 123, and now read 4, then 123*10=1230 then 1230+4=1234 */
else if(n==IN) {
num *= 10;
num += (int)ch-(int)'0';
}
/* If we are in n = DECIMAL, that is reading a decimal */
else {
count_decplaces++; /* Moving in to next decimal place, increment the number of decimal places */
/* Divide the digit to the 10th power of the number of decimal places eg. 2 in 3rd decimal place then 0.002 would be added */
num += ((int)ch-(int)'0')/pow(10, count_decplaces);
}
}
/* In case a decimal point is detected and it's not illegaly used period(.), i.e. double(.) or so */
else if(ch=='.' && n != DECIMAL) {
if(n==OUT) {
num = 0.0; /* In case if user inputs, .23, then sets num = 0.0 */
}
n=DECIMAL; /* Set n as DECIMAL, i.e. it will read as decimal state */
}
/* If we detect ch as any other character which is neither numeric nor single period */
else {
/* If we are reading the current number, then we finish reading it here */
if(n==IN || n==DECIMAL) {
if(sign == NEGATIVE) {
num *= -1;
}
sign = POSITIVE;
Stack_Push(&pfstack, num);
count_operands++;
}
/* Stop reading the number which was being read */
n = OUT;
count_decplaces=0;
/* If an operator is detected */
if(ch=='+' || ch=='-' || ch=='*' || ch=='/' || ch=='^') {
/*Pop top two elements, from the stack, if successfully popped, then move further */
if(Stack_Pop(&pfstack, &op1) && Stack_Pop(&pfstack,&op2)) {
switch(ch) {
/* Perform appropraite operation */
case '+':
res = op2 + op1;
break;
case '-':
res = op2 - op1;
break;
case '*':
res = op2 * op1;
break;
case '/':
if(op1 == 0) {
printf("ERROR: Divide by zero\n");
return;
}
res = op2 / op1;
break;
case '^':
res = pow(op2, op1);
break;
}
Stack_Push(&pfstack, res); /* Push the result onto the stack */
}
/* In case there is underflow in the stack, that means there were too many operators for current number of operands */
else {
printf("ERROR: Too less operands\n");
return;
}
}
/* ' ' is the seperator between numbers, it has to be noted operators can acts as separators too */
else if(ch==' ')
continue;
/* Any other character other than numeric, operator, or ' ' is invalid */
else {
printf("ERROR: Invalid Token\n");
return;
}
}
}
Stack_Pop(&pfstack, &res); /* Pop the (hopefully) last element, this is the result */
/* If an element still remains after the previous popping operations it means, there were excess of operands */
/* In case of failure of popping, which means successful parsing, res does not change its values during this code */
if(Stack_Pop(&pfstack, &res)) {
printf("ERROR: Too many operands\n");
return;
}
/* Output nothing if the number of operands is zero */
if(count_operands==0) {
return;
}
/* Show the result */
printf("%f\n", res);
}
int main()
{
char inp[LEN];
printf("Welcome to Post Fix Interpreter. Press q to quit\n\n");
while(1) {
printf("postfix> "); /* Prompt */
get_string(inp);
if(inp[0] == 'q')
break;
compute(inp); /* Evaluate */
}
printf("\n");
return 0;
}
Adv Reply
Originally Posted by vik_2010
Bookmarks