Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Prefix, Infix, Postfix Expression Processor
/**
* 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
You can’t perform that action at this time.