Created
October 24, 2018 00:11
-
-
Save jincongho/24fed1964892a25c94b6e72810aa21c4 to your computer and use it in GitHub Desktop.
Prefix, Infix, Postfix Expression Processor
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* Prefix, Infix, Postfix Expression Processor | |
* | |
* Functions: | |
* 1. Convert between prefix (Normal Polish Notation), expression, postfix (Reverse Polish Notation) | |
* 2. Evaluate value of any expression format, support *float* | |
* 3. Show detailed error message and *location* of invalid elements in expressions | |
*. 4. Read from files containing multiple expressions | |
* | |
* In place error reporting: | |
* 1. Invalid expression elements | |
* 2. Imbalance parenthesis | |
* 3. Imbalance operands and operators | |
* 4. Zero Division | |
* | |
* Notes: | |
* while it is better to declare variable once and reuse in all loops, | |
* all variables are declared inline as needed to improve readability | |
* | |
* Expression Examples: "( 3 + 4 ) * ( 100 ^ 2 )" | |
*/ | |
#include <stdio.h> | |
#include <stdlib.h> | |
#include <string.h> | |
#include <math.h> | |
#include <ctype.h> | |
#define MAX_OPERATORS 10 | |
#define MAX_OPERANDS 10 | |
#define MAX_BUFFER 100 //max buffer from user input | |
#define KEYBOARD_INPUT "kin.txt" //default file to save keyboard input | |
#define KEYBOARD_OUTPUT "kout.txt" //default file to save keyboard output | |
#define FILE_INPUT "default.txt" //default file to read from, and value of expressions will save back to the file | |
/** | |
* Expression Node, Node Tag, Node Data, Node Data Type | |
* | |
* Usage: store single element from expression, | |
* can contain string, int or float data, | |
* tagged with type for easier expresssion processing, | |
* data type is useful for printing and arithmetics, | |
* can be used to form array of struct or stack of struct. | |
*/ | |
typedef enum{ | |
ENT_DEFAULT, | |
ENT_OPERATOR, | |
ENT_OPENPR, | |
ENT_CLOSEPR, | |
ENT_OPERAND | |
} ExpNodeTag; | |
typedef union{ | |
char *string; | |
int integer; | |
float real; | |
} ExpNodeData; | |
typedef enum{ | |
ENDT_STRING, | |
ENDT_INTEGER, | |
ENDT_FLOAT | |
} ExpNodeDataType; | |
typedef struct element{ | |
ExpNodeTag tag; | |
ExpNodeData data; | |
ExpNodeDataType type; | |
struct element *next; | |
} ExpNode, *ExpNodePtr; | |
/** | |
* Operations on Expression Node | |
* Common logic on node creation and stack | |
*/ | |
ExpNodePtr node_create_str (ExpNodeTag tag, char* value); | |
ExpNodePtr node_create_flo (ExpNodeTag tag, float value); | |
ExpNodePtr node_create_int (ExpNodeTag tag, int value); | |
void node_print (ExpNodePtr node, FILE *stream); | |
void node_destroy (ExpNodePtr *node); | |
int stack_is_empty (ExpNodePtr head); | |
void stack_push (ExpNodePtr *head, ExpNodePtr node); | |
ExpNodePtr stack_pop (ExpNodePtr *head); | |
void stack_print (ExpNodePtr head, const char *delimiter, FILE *stream); | |
void stack_destroy (ExpNodePtr *head); | |
/** | |
* Operations to clean and validate inputs | |
* Tagging speed up identification in conversion | |
*/ | |
char *fscanAll (FILE *stream); | |
int get_expression (ExpNodePtr *expression, FILE *inputSourcePtr, FILE *inputFilePtr, int inputSource); | |
ExpNodePtr tag_expression (ExpNodePtr *expression, int length); | |
int detect_expression (ExpNodePtr *expression, int length); | |
ExpNodePtr validate_parentheses(ExpNodePtr *expression, int length, int format); | |
void show_error (ExpNodePtr *expression, ExpNodePtr position, char *message, int offset); | |
/** | |
* Operations to convert expression format | |
*/ | |
int precedence (ExpNodePtr node, int from_stack); | |
ExpNodePtr prefix_to_postfix (ExpNodePtr *expression, int *length, ExpNodePtr *output); | |
ExpNodePtr infix_to_postfix (ExpNodePtr *expression, int *length, ExpNodePtr *output); | |
ExpNodePtr postfix_to_postfix (ExpNodePtr *expression, int length, ExpNodePtr *output); | |
int postfix_to_expression (ExpNodePtr *expression, int length, ExpNodePtr *output, int type); | |
/** | |
* Operations to evaluate postfix expression | |
*/ | |
ExpNodePtr eval_postfix (ExpNodePtr *expression, int length, ExpNodePtr *output); | |
float eval_op (char operator, float f1, float f2); | |
/** | |
* Program Entry Point | |
* | |
* Process: | |
* Program Loop -> Expression Loop -> Action Loop | |
*/ | |
int main() | |
{ | |
printf("Welcome to Prefix-Infix-Postfix Converter!\n"); | |
/** | |
* Program Loop | |
* Request user to choose input source | |
* Exit when exit_program == 1 | |
*/ | |
int exit_program = 0; | |
do{ | |
//input source menu | |
printf("\nWhere do you want to read expressions from?\n" | |
"A. Text File\n" | |
"B. Keyboard\n" | |
"? "); | |
char *choice = fscanAll(stdin); | |
//0 for keyboard, 1 for file | |
int inputSource; | |
//stream to read from | |
FILE *inputSourcePtr; | |
//stream to save input | |
FILE *inputFilePtr; | |
//stream to save output | |
FILE *outputFilePtr; | |
//prepare input stream | |
//use strcmp instead of switch to compare whole string | |
//eg: As, B1, A s, a9, etc will not be misinterpreted | |
if(strcmp("A", choice) == 0){ | |
printf("\nYour file can contain multiple lines, " | |
"each represents an expression.\n" | |
"Text file location (press enter to use default input file at %s):\n? ", FILE_INPUT); | |
char *filename = fscanAll(stdin); | |
//use default file location | |
if(filename[0] == '\0') | |
filename = FILE_INPUT; | |
inputSource = 1; | |
if((inputSourcePtr = fopen(filename, "r+")) == NULL){ | |
printf("Error: Cannot open %s to read expressions.\n", filename); | |
continue; | |
} | |
inputFilePtr = NULL; | |
if((outputFilePtr = fopen(filename, "a+")) == NULL){ | |
printf("Error: Cannot open %s to save program output.\n", filename); | |
continue; | |
} | |
printf("Hint: Program will read from %s and write back to the file. Output will be flushed only if program is exited properly.\n", filename); | |
}else if(strcmp("B", choice) == 0){ | |
inputSource = 0; | |
inputSourcePtr = stdin; | |
if((inputFilePtr = fopen(KEYBOARD_INPUT, "a+")) == NULL){ | |
printf("Error: Cannot open %s to save keyboard input.\n", KEYBOARD_INPUT); | |
continue; | |
} | |
if((outputFilePtr = fopen(KEYBOARD_OUTPUT, "a+")) == NULL){ | |
printf("Error: Cannot open %s to save program output.\n", KEYBOARD_OUTPUT); | |
continue; | |
} | |
printf("Hint: Program will save keyboard input to %s and output to %s. File content will be flushed only if program is exited properly.\n", KEYBOARD_INPUT, KEYBOARD_OUTPUT); | |
}else{ | |
printf("Choice unrecognised.\n"); | |
continue; | |
} | |
free(choice); | |
/** | |
* Expression Loop | |
* Read an expression from stream | |
* Exit when change_input == 1 | |
*/ | |
int change_input = 0, file_error = 0; | |
do{ | |
//confirm continue or not if last loop ended in | |
//error reading expression from file | |
if(file_error){ | |
file_error = 0; | |
printf("\nDo you want to stop reading from file (Y/N)?\n? "); | |
char *stop = fscanAll(stdin); | |
if(strcmp("Y", stop) == 0){ | |
change_input = 1; | |
free(stop); | |
continue; | |
} | |
free(stop); | |
} | |
//buffer to store expression | |
ExpNodePtr *expression = malloc(sizeof(ExpNodePtr)*(MAX_OPERATORS*3+MAX_OPERANDS)); | |
memset(expression, 0, MAX_OPERATORS*3+MAX_OPERANDS); | |
//offset when printing error message | |
int errorOffset = (inputSource == 0) ? 3 : 12; | |
//get expression | |
if(inputSource == 0) | |
printf("\nWhat expression do you want to work on?" | |
"\nAccept: %i operands from -99 to 99, %i operators from +-*/^(), space seperated" | |
"\n?: ", MAX_OPERANDS, MAX_OPERATORS); | |
int length = get_expression(expression, inputSourcePtr, inputFilePtr, inputSource); | |
if(length == 0){ | |
printf("Error: expression is empty.\n"); | |
if(inputSource == 1) | |
file_error = 1; | |
continue; | |
}else if(length == -1){ | |
printf("Error: expression is too long.\n"); | |
if(inputSource == 1) | |
file_error = 1; | |
continue; | |
} | |
/** | |
* Error Checking: Expression Elements | |
* Tag and validate expression elements | |
* eg: (9, +-, a8, a8 | |
*/ | |
ExpNodePtr val_el = tag_expression(expression, length); | |
if(val_el != NULL){ | |
show_error(expression, val_el, "Error: invalid element.", errorOffset); | |
if(inputSource == 1) | |
file_error = 1; | |
continue; | |
} | |
//detect expression format | |
int format = detect_expression(expression, length); | |
/** | |
* Error Checking: Imbalance Parenthesis | |
* eg: ), (, )(, ()), (() | |
*/ | |
ExpNodePtr val_parentheses = validate_parentheses(expression, length, format); | |
if(val_parentheses != NULL){ | |
if(val_parentheses->tag == ENT_OPENPR){ | |
show_error(expression, val_parentheses, "Error: Ops, you didn't close this parenthesis.", errorOffset); | |
}else{ | |
show_error(expression, val_parentheses, "Error: invalid parenthesis.", errorOffset); | |
} | |
continue; | |
} | |
//buffer to store postfix as intermediate format | |
ExpNodePtr *postfix = malloc(sizeof(ExpNodePtr)*(MAX_OPERATORS*3+MAX_OPERANDS)); | |
memset(postfix, 0, MAX_OPERATORS*3+MAX_OPERANDS); | |
ExpNodePtr convert = NULL; | |
switch(format){ | |
case -1: | |
convert = prefix_to_postfix(expression, &length, postfix); | |
break; | |
case 0: | |
convert = infix_to_postfix(expression, &length, postfix); | |
break; | |
case 1: | |
//still need to validate imbalance operand and operators | |
convert = postfix_to_postfix(expression, length, postfix); | |
break; | |
} | |
/** | |
* Error Checking: Imbalance Operand and Operator | |
* prefix : + 9 9 9, + + 9 9, + + + 9 9 + 9 9 | |
* infix : 9 9 + 9, ( 9 9 ) + 9, 9 + 9 9, 9 + ( 9 9 ) | |
* postfix : 9 9 9 +, 9 9 + +, 9 9 + 9 9 + + + | |
*/ | |
if(convert != NULL){ | |
if(convert->tag == ENT_OPERATOR){ | |
show_error(expression, convert, "Error: not enough operand.", errorOffset); | |
}else{ | |
show_error(expression, convert, "Error: excess operand.", errorOffset); | |
} | |
continue; | |
} | |
/** | |
* Error Checking: Zero Devision | |
* Precalculate expression value | |
* eg: 8 / 0, 20 / ( 8 - 8 ) | |
*/ | |
ExpNodePtr result, eval; | |
if((eval = eval_postfix(postfix, length, &result)) != NULL){ | |
show_error(expression, eval, "Error: zero division at here.", errorOffset); | |
continue; | |
} | |
/** | |
* Actions Loop | |
* Execute actions on expressions | |
* Exit when exit_menu == 1 | |
*/ | |
int exit_menu = 0; | |
do{ | |
//actions menu | |
printf("\nPlease select an action: \n" | |
"A. Convert to infix, prefix or postfix \n" | |
"B. Evaluate expression\n" | |
"C. %s\n" | |
"D. Change Input Method\n" | |
"E. Exit Program\n?: ", | |
(inputSource == 0) ? "Enter new expression" : "Get next expression from file"); | |
char *choice2 = fscanAll(stdin); | |
//convert format | |
if(strcmp("A", choice2) == 0){ | |
//buffer for convertion | |
ExpNodePtr *convert_a = malloc(sizeof(ExpNodePtr)*(MAX_OPERATORS*3+MAX_OPERANDS)); | |
memset(convert_a, 0, MAX_OPERATORS*3+MAX_OPERANDS); | |
ExpNodePtr *convert_b = malloc(sizeof(ExpNodePtr)*(MAX_OPERATORS*3+MAX_OPERANDS)); | |
memset(convert_b, 0, MAX_OPERATORS*3+MAX_OPERANDS); | |
//use modulus to choose 0(prefix), 1(infix), 2(postfix) | |
char format_labels[3][8] = {"prefix", "infix", "postfix"}; | |
int current = (format+1); | |
int a = (current+1)%3; | |
int b = (current+2)%3; | |
printf("\nThis is a(n) %s expression. Do you want to convert it to (A) %s or (B) %s or (C) for both? Select A, B, or C option.\n?: ", format_labels[current], format_labels[a], format_labels[b]); | |
char *choice3 = fscanAll(stdin); | |
//calculate conversion based on modulus result | |
int l_a = postfix_to_expression(postfix, length, convert_a, a-1); | |
int l_b = postfix_to_expression(postfix, length, convert_b, b-1); | |
if(strcmp("A", choice3) == 0){ | |
printf("\nThe %s format is: ", format_labels[a]); | |
fprintf(outputFilePtr, "\nThe %s format is: ", format_labels[a]); | |
for(int i=0; i<l_a; i++){ | |
node_print(convert_a[i], stdout); | |
node_print(convert_a[i], outputFilePtr); | |
printf(" "); | |
fprintf(outputFilePtr, " "); | |
} | |
printf("\n"); | |
}else if(strcmp("B", choice3) == 0){ | |
printf("\nThe %s format is: ", format_labels[b]); | |
fprintf(outputFilePtr, "\nThe %s format is: ", format_labels[b]); | |
for(int i=0; i<l_b; i++){ | |
node_print(convert_b[i], stdout); | |
node_print(convert_b[i], outputFilePtr); | |
printf(" "); | |
fprintf(outputFilePtr, " "); | |
} | |
printf("\n"); | |
}else if(strcmp("C", choice3) == 0){ | |
printf("\nThe %s format is: ", format_labels[a]); | |
fprintf(outputFilePtr, "\nThe %s format is: ", format_labels[a]); | |
for(int i=0; i<l_a; i++){ | |
node_print(convert_a[i], stdout); | |
node_print(convert_a[i], outputFilePtr); | |
printf(" "); | |
fprintf(outputFilePtr, " "); | |
} | |
printf("\nThe %s format is: ", format_labels[b]); | |
fprintf(outputFilePtr, "\nThe %s format is: ", format_labels[b]); | |
for(int i=0; i<l_b; i++){ | |
node_print(convert_b[i], stdout); | |
node_print(convert_b[i], outputFilePtr); | |
printf(" "); | |
fprintf(outputFilePtr, " "); | |
} | |
printf("\n"); | |
}else{ | |
printf("\nChoice unrecognised.\n"); | |
} | |
free(convert_a); | |
free(convert_b); | |
free(choice3); | |
//evaluate value | |
}else if(strcmp("B", choice2) == 0){ | |
printf("\nThe value of this expression is: "); | |
fprintf(outputFilePtr, "\nThe value of this expression is: "); | |
node_print(result, stdout); | |
node_print(result, outputFilePtr); | |
printf("\n"); | |
//next expression | |
}else if(strcmp("C", choice2) == 0){ | |
exit_menu = 1; | |
//change input source | |
}else if(strcmp("D", choice2) == 0){ | |
exit_menu = 1; | |
change_input = 1; | |
//exit program | |
}else if(strcmp("E", choice2) == 0){ | |
exit_menu = 1; | |
change_input = 1; | |
exit_program = 1; | |
}else{ | |
printf("\nChoice unrecognised.\n"); | |
} | |
free(choice2); | |
}while(exit_menu == 0); | |
for(int i=0; (i<(MAX_OPERATORS*3+MAX_OPERANDS)) && (expression[i]!=NULL); i++) | |
node_destroy(&expression[i]); | |
free(expression); | |
free(postfix); | |
}while(change_input == 0); | |
//close files | |
if(inputSource == 0){ | |
fclose(inputSourcePtr); | |
fclose(outputFilePtr); | |
}else if(inputSource == 1){ | |
fclose(inputFilePtr); | |
fclose(outputFilePtr); | |
} | |
}while(exit_program == 0); | |
printf("\nThanks for using our converter!\n"); | |
} | |
/** | |
* FscanAll | |
* scanf(" %s") cannot accepts string with space, | |
* if more character than expected, will left in buffer | |
* and affect next reading | |
* @return pointer to character receive | |
* @warning must free returned char* after use | |
*/ | |
char *fscanAll(FILE *stream) | |
{ | |
char *all = calloc(256, sizeof(char)), *tmp, c; | |
size_t size = 0, index = 0, chunk = 256; | |
while ((c = fgetc(stream)) != '\n' && !feof(stream)) { | |
//dynamically resize memory | |
if(size <= index){ | |
size += chunk; | |
tmp = realloc(all, size); | |
memset(tmp+(size-chunk), 0, chunk); | |
if(!tmp){ | |
free(all); | |
all = NULL; | |
break; | |
} | |
all = tmp; | |
} | |
all[index++] = c; | |
} | |
return all; | |
} | |
/** | |
* Retrieve and tokenize expression | |
* | |
* @return -1 if more operators or operands than allowed | |
* otherwise amount of operators and operands | |
*/ | |
int get_expression(ExpNodePtr *expression, FILE *inputSourcePtr, FILE *inputFilePtr, int inputSource) | |
{ | |
char *btoken, delim[2] = " "; | |
int i = -1; | |
//retrieve input from stream | |
char *buffer = fscanAll(inputSourcePtr); | |
//save keyboard input when read from default input | |
if(inputSource == 0) | |
fprintf(inputFilePtr, "%s\n", buffer); | |
//output expression if is read from file | |
if(inputSource == 1) | |
fprintf(stdout, "\nExpression: %s\n", buffer); | |
//trim trailing space | |
int bi = (int) strlen(buffer)-1; | |
while(isspace(buffer[bi])) | |
buffer[bi--] = 0; | |
//tokenize input | |
btoken = strtok(buffer, delim); | |
while(btoken != NULL) | |
{ | |
if(++i > MAX_OPERANDS+MAX_OPERATORS) | |
return -1; | |
expression[i] = node_create_str(ENT_DEFAULT, btoken); | |
btoken = strtok(NULL, delim); | |
} | |
free(buffer); | |
return i+1; | |
}; | |
/** | |
* Tag and Validate Expression | |
* | |
* @return NULL if no error | |
* ppinter of invalid element if error | |
*/ | |
ExpNodePtr tag_expression(ExpNodePtr *expression, int length) | |
{ | |
for(int i=0; i<length; i++){ | |
int first_negative = (expression[i]->data.string[0] == '-'); | |
int first_operator = (memchr("^*/+", expression[i]->data.string[0], 4) != NULL); | |
int first_openpr = (expression[i]->data.string[0] == '('); | |
int first_closepr = (expression[i]->data.string[0] == ')'); | |
int exp_length = (int) strlen(expression[i]->data.string); | |
int all_digits = 1; | |
int neg_digits = 1; | |
for(int j=0; expression[i]->data.string[j]!='\0'; j++){ | |
if(!isdigit(expression[i]->data.string[j])){ | |
all_digits = 0; | |
if(j!=0){ | |
neg_digits = 0; | |
break; | |
} | |
} | |
} | |
if(first_openpr && (exp_length == 1)){ | |
expression[i]->tag = ENT_OPENPR; | |
}else if(first_closepr && (exp_length == 1)){ | |
expression[i]->tag = ENT_CLOSEPR; | |
}else if((first_operator || first_negative) && (exp_length == 1)){ | |
expression[i]->tag = ENT_OPERATOR; | |
}else if((first_negative && neg_digits) || all_digits){ | |
//destroy original string node and create an int node | |
int value = atoi(expression[i]->data.string); | |
node_destroy(&expression[i]); | |
expression[i] = node_create_int(ENT_OPERAND, value); | |
}else{ | |
return expression[i]; | |
} | |
} | |
return NULL; | |
}; | |
/** | |
* Detect Expression Format | |
* | |
* @return -1 if is prefix | |
* 0 if is infix expression | |
* 1 if is postfix | |
*/ | |
int detect_expression (ExpNodePtr *expression, int length) | |
{ | |
//prefix: return -1 if first character is operator | |
for(int i=0; i<length; i++){ | |
if(expression[i]->tag == ENT_OPENPR) | |
continue; | |
if(expression[i]->tag == ENT_OPERATOR) | |
return -1; | |
else | |
break; | |
} | |
//postfix: return 1 if last character is operator | |
for(int i=(length-1); i>=0; i--){ | |
if(expression[i]->tag == ENT_CLOSEPR) | |
continue; | |
if(expression[i]->tag == ENT_OPERATOR) | |
return 1; | |
else | |
break; | |
} | |
//otherwise infix expression | |
return 0; | |
}; | |
/** | |
* Validate Parentheses in Expression | |
* | |
* @return NULL if is balanced | |
* pointer of invalid parenthesis if is imbalanced | |
*/ | |
ExpNodePtr validate_parentheses(ExpNodePtr *expression, int length, int format) | |
{ | |
ExpNodePtr prtrace = NULL, pop; | |
for(int i=0; i<length; i++){ | |
//only infix expression can contain parenthesis | |
if((format != 0) && ((expression[i]->tag == ENT_OPENPR) || (expression[i]->tag == ENT_CLOSEPR))) | |
return expression[i]; | |
if(expression[i]->tag == ENT_OPENPR){ | |
stack_push(&prtrace, node_create_int(ENT_DEFAULT, i)); | |
}else if((expression[i]->tag == ENT_CLOSEPR) && (stack_is_empty(prtrace))){ | |
return expression[i]; | |
}else if(expression[i]->tag == ENT_CLOSEPR){ | |
pop = stack_pop(&prtrace); | |
node_destroy(&pop); | |
} | |
} | |
ExpNodePtr r = stack_is_empty(prtrace) ? NULL : expression[prtrace->data.integer]; | |
stack_destroy(&prtrace); | |
return r; | |
}; | |
/** | |
* Show Error | |
* Print space until the position of the incorrect element | |
* Then, print arrow and error message | |
*/ | |
void show_error (ExpNodePtr *expression, ExpNodePtr position, char *message, int offset) | |
{ | |
for(int i=0;i<offset;i++) | |
printf(" "); | |
int length = 0; | |
for(int i=0;expression[i] != position;i++){ | |
switch(expression[i]->type){ | |
case ENDT_INTEGER: | |
if(expression[i]->data.integer == 0){ | |
length = 1; | |
}else{ | |
length = floor(log10(abs(expression[i]->data.integer)))+1; | |
if(expression[i]->data.integer < 0) | |
length++; | |
} | |
break; | |
case ENDT_STRING: | |
length = (int) strlen(expression[i]->data.string); | |
break; | |
default: | |
break; | |
} | |
for(int j=0;j<length;j++) | |
printf(" "); | |
printf(" "); | |
} | |
printf("^\n%s\n", message); | |
}; | |
/** | |
* Return Operator's Precedence | |
* | |
* @return operator's precedence | |
*/ | |
int precedence(ExpNodePtr node, int from_stack) | |
{ | |
if(from_stack && (node->tag == ENT_OPENPR)) | |
return 1; | |
switch(node->data.string[0]) | |
{ | |
case '(': | |
return 5; | |
case '^': | |
return 4; | |
case '*': | |
case '/': | |
return 3; | |
case '+': | |
case '-': | |
return 2; | |
default: | |
return 0; | |
} | |
}; | |
/** | |
* Prefix to Postfix Conversion | |
* | |
* @reference: http://www.manojagarwal.co.in/conversion-from-prefix-to-postfix/ | |
* @return pointer of invalid element | |
* NULL if no error | |
*/ | |
ExpNodePtr prefix_to_postfix(ExpNodePtr *expression, int *length, ExpNodePtr *output) | |
{ | |
ExpNodePtr op1 = NULL, op2 = NULL, optrace = NULL, pop; | |
int oi = 0; | |
for(int i=(*length)-1; i>=0; i--){ | |
if(expression[i]->tag == ENT_OPERAND){ | |
output[oi++] = expression[i]; | |
stack_push(&optrace, node_create_int(ENT_DEFAULT, i)); | |
}else if(expression[i]->tag == ENT_OPERATOR){ | |
int pc = 0; | |
do{ | |
if((--oi<0) || (output[oi]==NULL)) return expression[i]; | |
ExpNodePtr top = output[oi]; | |
if(top->tag == ENT_CLOSEPR) pc++; | |
if(top->tag == ENT_OPENPR) pc--; | |
stack_push(&op1, top); | |
}while(pc > 0); | |
pop = stack_pop(&optrace); | |
node_destroy(&pop); | |
pc = 0; | |
do{ | |
if((--oi<0) || (output[oi]==NULL)) return expression[i]; | |
ExpNodePtr top = output[oi]; | |
if(top->tag == ENT_CLOSEPR) pc++; | |
if(top->tag == ENT_OPENPR) pc--; | |
stack_push(&op2, top); | |
}while(pc > 0); | |
pop = stack_pop(&optrace); | |
node_destroy(&pop); | |
//put '(' | |
output[oi++] = node_create_str(ENT_OPENPR, "("); | |
//operand 1 | |
while(!stack_is_empty(op1)) | |
output[oi++] = stack_pop(&op1); | |
//operand 2 | |
while(!stack_is_empty(op2)) | |
output[oi++] = stack_pop(&op2); | |
//operator | |
output[oi++] = expression[i]; | |
//put ')' | |
output[oi++] = node_create_str(ENT_CLOSEPR, ")"); | |
stack_push(&optrace, node_create_int(ENT_DEFAULT, -1)); | |
} | |
} | |
//check operands | |
pop = optrace; | |
int r = -1; | |
while(pop != NULL){ | |
if(pop->data.integer == -1){ | |
pop = pop->next; | |
continue; | |
}else{ | |
r = pop->data.integer; | |
break; | |
} | |
} | |
stack_destroy(&optrace); | |
if(r!=-1) return expression[r]; | |
//remove brackets | |
ExpNodePtr temp = NULL; | |
while((--oi) >= 0){ | |
if((output[oi]->tag == ENT_OPENPR) || (output[oi]->tag == ENT_CLOSEPR)) | |
node_destroy(&output[oi]); | |
else | |
stack_push(&temp, output[oi]); | |
output[oi] = NULL; | |
} | |
while(!stack_is_empty(temp)) | |
output[++oi] = stack_pop(&temp); | |
*length = ++oi; | |
return NULL; | |
} | |
/** | |
* Infix to Postfix Conversion | |
* | |
* @reference: stack.pdf by Mr. Chew | |
* @return pointer of invalid element | |
* NULL if no error | |
*/ | |
ExpNodePtr infix_to_postfix(ExpNodePtr *expression, int *length, ExpNodePtr *output) | |
{ | |
ExpNodePtr operators = NULL; | |
int oi = 0, last_element = -1; | |
for(int i=0; i<(*length); i++){ | |
switch(expression[i]->tag){ | |
case ENT_OPERAND: | |
output[oi++] = expression[i]; | |
if(last_element == 0) | |
return expression[i]; | |
else | |
last_element = 0; | |
break; | |
case ENT_OPERATOR: | |
case ENT_OPENPR: | |
if(!stack_is_empty(operators)){ | |
while((!stack_is_empty(operators)) && (precedence(expression[i],0) <= precedence(operators,1))){ | |
if(operators->tag != ENT_OPENPR) | |
output[oi++] = stack_pop(&operators); | |
} | |
} | |
stack_push(&operators, expression[i]); | |
if(expression[i]->tag == ENT_OPERATOR){ | |
if(last_element == 1) | |
return expression[i]; | |
else | |
last_element = 1; | |
} | |
break; | |
case ENT_CLOSEPR: | |
while(operators->tag != ENT_OPENPR) | |
output[oi++] = stack_pop(&operators); | |
stack_pop(&operators); | |
break; | |
default: | |
continue; | |
} | |
} | |
while(!stack_is_empty(operators)) | |
output[oi++] = stack_pop(&operators); | |
*length = oi; | |
return NULL; | |
}; | |
/** | |
* Postfix Validation and Zero Division Prevent | |
* | |
* @reference: stack.pdf by Mr. Chew | |
* @return pointer of invalid element | |
* -1 if no error | |
*/ | |
ExpNodePtr postfix_to_postfix(ExpNodePtr *expression, int length, ExpNodePtr *postfix) | |
{ | |
ExpNodePtr optrace = NULL, pop; | |
for(int i=0; i<length; i++){ | |
postfix[i] = expression[i]; | |
if(expression[i]->tag == ENT_OPERAND){ | |
stack_push(&optrace, node_create_int(ENT_DEFAULT, i)); | |
}else if(expression[i]->tag == ENT_OPERATOR){ | |
if(stack_is_empty(optrace)) return expression[i]; | |
pop = stack_pop(&optrace); | |
node_destroy(&pop); | |
if(stack_is_empty(optrace)) return expression[i]; | |
pop = stack_pop(&optrace); | |
node_destroy(&pop); | |
stack_push(&optrace, node_create_int(ENT_DEFAULT, -1)); | |
} | |
} | |
//check operands | |
pop = optrace; | |
int r = -1; | |
while(pop != NULL){ | |
if(pop->data.integer == -1){ | |
pop = pop->next; | |
continue; | |
}else{ | |
r = pop->data.integer; | |
break; | |
} | |
} | |
stack_destroy(&optrace); | |
if(r!=-1) return expression[r]; | |
return NULL; | |
} | |
/** | |
* Postfix to Prefix/Infix Conversion | |
* | |
* @param type -1 to convert into prefix; 0 to convert into infix; 1 to retain postfix | |
* @reference: http://rubyquiz.com/quiz148.html | |
* @reference: http://see-programming.blogspot.my/2013/05/postfix-to-prefix-conversion.html | |
*/ | |
int postfix_to_expression (ExpNodePtr *expression, int length, ExpNodePtr *output, int type) | |
{ | |
if(type == 1){ | |
for(int i=0; i<length; i++) | |
output[i] = expression[i]; | |
return length; | |
} | |
ExpNodePtr op1 = NULL, op2 = NULL; | |
int oi = 0; | |
for(int i=0; i<length; i++){ | |
if(expression[i]->tag == ENT_OPERAND){ | |
output[oi++] = expression[i]; | |
}else if(expression[i]->tag == ENT_OPERATOR){ | |
int pc = 0; | |
do{ | |
ExpNodePtr top = output[--oi]; | |
if(top->tag == ENT_CLOSEPR) pc++; | |
if(top->tag == ENT_OPENPR) pc--; | |
stack_push(&op2, top); | |
}while(pc > 0); | |
pc = 0; | |
do{ | |
ExpNodePtr top = output[--oi]; | |
if(top->tag == ENT_CLOSEPR) pc++; | |
if(top->tag == ENT_OPENPR) pc--; | |
stack_push(&op1, top); | |
}while(pc > 0); | |
//put '(' | |
output[oi++] = node_create_str(ENT_OPENPR, "("); | |
//put operator in front if is prefix | |
if(type == -1) | |
output[oi++] = expression[i]; | |
//operand 1 | |
while(!stack_is_empty(op1)) | |
output[oi++] = stack_pop(&op1); | |
//put operator in middle if is prefix | |
if(type == 0) | |
output[oi++] = expression[i]; | |
//operand 2 | |
while(!stack_is_empty(op2)) | |
output[oi++] = stack_pop(&op2); | |
//put ')' | |
output[oi++] = node_create_str(ENT_CLOSEPR, ")"); | |
} | |
} | |
//remove brackets if is prefix | |
if(type == -1){ | |
ExpNodePtr temp = NULL; | |
while((--oi) >= 0){ | |
if((output[oi]->tag == ENT_OPENPR) || (output[oi]->tag == ENT_CLOSEPR)) | |
node_destroy(&output[oi]); | |
else | |
stack_push(&temp, output[oi]); | |
output[oi] = NULL; | |
} | |
while(!stack_is_empty(temp)) | |
output[++oi] = stack_pop(&temp); | |
++oi; | |
} | |
return oi; | |
} | |
/** | |
* Evaluate Postfix Expression | |
* | |
* @reference: stack.pdf by Mr. Chew | |
* @return pointer to node that leads to zero division | |
* else pointer to node that contains the value | |
*/ | |
ExpNodePtr eval_postfix (ExpNodePtr *expression, int length, ExpNodePtr *output){ | |
ExpNodePtr operands = NULL, op1, op2; | |
for(int i=0; i<length; i++){ | |
if(expression[i]->tag == ENT_OPERAND){ | |
stack_push(&operands, expression[i]); | |
}else if(expression[i]->tag == ENT_OPERATOR){ | |
float f1=0, f2=0, result=0; | |
char operator = expression[i]->data.string[0]; | |
op2 = stack_pop(&operands); | |
switch(op2->type){ | |
case ENDT_INTEGER: | |
f2 = op2->data.integer; | |
break; | |
case ENDT_FLOAT: | |
f2 = op2->data.real; | |
break; | |
default: | |
break; | |
} | |
if((f2 == 0.0) && (operator == '/')) | |
return expression[i]; | |
op1 = stack_pop(&operands); | |
switch(op1->type){ | |
case ENDT_INTEGER: | |
f1 = op1->data.integer; | |
break; | |
case ENDT_FLOAT: | |
f1 = op1->data.real; | |
break; | |
default: | |
break; | |
} | |
result = eval_op(operator, f1, f2); | |
stack_push(&operands, node_create_flo(ENT_OPERAND, result)); | |
} | |
} | |
*output = operands; | |
return NULL; | |
}; | |
/** | |
* Evaluate Arithmetic Operation | |
* | |
* @return value of operation | |
* 0 otherwise | |
*/ | |
float eval_op (char operator, float f1, float f2){ | |
switch(operator) | |
{ | |
case '^': | |
return pow(f1, f2); | |
case '*': | |
return f1*f2; | |
case '/': | |
return f1/f2; | |
case '+': | |
return f1+f2; | |
case '-': | |
return f1-f2; | |
default: | |
return 0; | |
} | |
}; | |
/** | |
* Create a string node | |
*/ | |
ExpNodePtr node_create_str (ExpNodeTag tag, char* value) | |
{ | |
ExpNodePtr create = malloc(sizeof(ExpNode)); | |
create->tag = tag; | |
create->data.string = malloc(sizeof(char)*strlen(value)); | |
strcpy(create->data.string, value); | |
create->type = ENDT_STRING; | |
create->next = NULL; | |
return create; | |
}; | |
/** | |
* Create an int node | |
*/ | |
ExpNodePtr node_create_int (ExpNodeTag tag, int value) | |
{ | |
ExpNodePtr create = malloc(sizeof(ExpNode)); | |
create->tag = tag; | |
create->data.integer = value; | |
create->type = ENDT_INTEGER; | |
create->next = NULL; | |
return create; | |
}; | |
/** | |
* Create a floating point node | |
*/ | |
ExpNodePtr node_create_flo (ExpNodeTag tag, float value) | |
{ | |
ExpNodePtr create = malloc(sizeof(ExpNode)); | |
create->tag = tag; | |
create->data.real = value; | |
create->type = ENDT_FLOAT; | |
create->next = NULL; | |
return create; | |
}; | |
/** | |
* Print out node based on data type | |
*/ | |
void node_print (ExpNodePtr node, FILE *stream) | |
{ | |
switch(node->type){ | |
case ENDT_STRING: | |
fprintf(stream, "%s", node->data.string); | |
break; | |
case ENDT_INTEGER: | |
fprintf(stream, "%i", node->data.integer); | |
break; | |
case ENDT_FLOAT: | |
fprintf(stream, "%.2f", node->data.real); | |
break; | |
} | |
}; | |
/** | |
* Release node memory | |
*/ | |
void node_destroy (ExpNodePtr *node) | |
{ | |
if((*node)->type == ENDT_STRING) | |
free((*node)->data.string); | |
free(*node); | |
}; | |
/** | |
* Check stack is empty or not | |
*/ | |
int stack_is_empty (ExpNodePtr head) | |
{ | |
return (head == NULL); | |
}; | |
/** | |
* Push a node to stack | |
*/ | |
void stack_push (ExpNodePtr *head, ExpNodePtr node) | |
{ | |
if(head != NULL) | |
node->next = *head; | |
*head = node; | |
}; | |
/** | |
* Pop a node from stack | |
*/ | |
ExpNodePtr stack_pop (ExpNodePtr *head) | |
{ | |
ExpNodePtr temp = *head; | |
if(*head!=NULL){ | |
*head = (*head)->next; | |
temp->next = NULL; | |
} | |
return temp; | |
}; | |
/** | |
* Print out stack | |
*/ | |
void stack_print (ExpNodePtr head, const char *delimeter, FILE *stream) | |
{ | |
while(head!=NULL){ | |
node_print(head, stream); | |
fprintf(stream, "%s", delimeter); | |
head = head->next; | |
} | |
}; | |
/** | |
* Release stack memory | |
*/ | |
void stack_destroy (ExpNodePtr *head) | |
{ | |
ExpNodePtr temp; | |
while(*head!=NULL){ | |
temp = (*head)->next; | |
node_destroy(head); | |
*head = temp; | |
} | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment