Файл infix2postfix.c

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <ctype.h>

#include "infix2postfix.h"

//Functions for getting items from Input string

//"item" is text which is separated by spaces or tabulations

struct StrArray

{

char** item; //array of strings

int counti; //count strings of the array

};

short add_item(struct StrArray* array, char* new_item)

{

char** ptr2=realloc(array->item,(array->counti+1)*sizeof(char*));

if(ptr2!= NULL)

array->item=ptr2;

else

{

printf("\nError: Can not resize array\n");

return -1;

}

array->item[array->counti]=(char*)calloc((MAX_ID_LEN+1),sizeof(char));

strcpy(array->item[array->counti],new_item);

array->counti++;

return 0;

}

void free_items(struct StrArray* array)

{

for(int i=0;i<array->counti;i++)

free(array->item[i]);

free(array->item);

}

//

//The function separetes items(words) from sting (s) and returns array with these items

void GetItems(const char* s, struct StrArray *InputItems)

{

int CurCh = 0;

short separat = 0; //flag for separating items

char CurItem[MAX_ID_LEN]; //for togethering one item

memset(CurItem,0,sizeof(CurItem)); //forclearing array

int CurCh_inNew = 0;

while(s[CurCh]!= '\0')

{

if(s[CurCh] == ' ' || s[CurCh] == '\t')

separat = 1;

else

{

if(separat == 1)

{

separat = 0;

if(CurCh_inNew!= 0) //for first item

{

add_item(&(*InputItems), CurItem);

CurCh_inNew = 0;

memset(CurItem,0,sizeof(CurItem));

}

}

CurItem[CurCh_inNew] = s[CurCh];

CurCh_inNew++;

}

CurCh++;

}

//for the latest item

if(CurCh_inNew!= 0)

add_item(&(*InputItems), CurItem);

}

//It converts string (s) to array of tokens

//return 0 in case of success

// -1 in case of wrong format of any token

// -2 in case of it can not resize array

int tokenize(const char *s, Token **tokens, int *len)

{

struct StrArray ItemsArray = {NULL,0}; //Array of tokens strings

GetItems(s, &ItemsArray); //Get this array

(*tokens)=(Token*)calloc(0,sizeof(Token));

for(int item_id=0;item_id < ItemsArray.counti;item_id++)

{

char* Item = ItemsArray.item[item_id];

Token* ptr2=realloc((*tokens),(++(*len))*sizeof(Token));

if(ptr2!= NULL)

(*tokens) = ptr2;

else

{

free_items(&ItemsArray);

return -2;

}

Token* CurToken = &(*tokens)[(*len)-1];

if(Item[1] == '\0' && (Item[0] == '+' || Item[0] == '-' || Item[0] == '*' || Item[0] == '/' || Item[0] == '(' || Item[0] == ')'))

{

CurToken->ttype = tt_OPER;

CurToken->tvalue.otype = Item[0];

//printf("\nIt is operator\n");

}

else

{

int CurChar = 1;

if(isdigit(Item[0]))

{

while(Item[CurChar]!= '\0')

{

if(!isdigit(Item[CurChar]))

{

free_items(&ItemsArray);

return -1;

}

CurChar++;

}

CurToken->ttype = tt_CONST;

CurToken->tvalue.inum = atoi(Item);

//printf("\nIt is number\n");

}

else if(isalpha(Item[0])!= 0)

{

while(Item[CurChar]!= '\0')

{

if(isalpha(Item[CurChar]) == 0 &&!isdigit(Item[CurChar]))

{

free_items(&ItemsArray);

return -1;

}

CurChar++;

}

CurToken->ttype = tt_ID;

strcpy(CurToken->tvalue.id, Item);

//printf("\nIt is name\n");

}

else

{

free_items(&ItemsArray);

return -1;

}

}

}

free_items(&ItemsArray);

return 0;

}

typedef struct

{

Token* items; //array of items

int count; //count items of the array

} TokensDArray;

//return 0 in case of success

// -1 in case of stack is over full

short push(TokensDArray *stack, const Token *token)

{

Token* ptr2=realloc((*stack).items,(++(*stack).count)*sizeof(Token));

if(ptr2!= NULL)

(*stack).items = ptr2;

else

return -1;

(*stack).items[(*stack).count-1] = (*token);

return 0;

}

//return <Current Count stack item> in case of success

// -1 in case of can not resize array

short pop(TokensDArray *stack, Token **TokensArray, int *len)

{

if((*stack).count > 0)

{

Token* ptr2=realloc((*TokensArray),(++(*len))*sizeof(Token));

if(ptr2!= NULL)

(*TokensArray) = ptr2;

else

return -1;

(*TokensArray)[(*len)-1]=(*stack).items[--(*stack).count];

}

return (*stack).count;

}

//return 0 in case of success

// -1 in case of can not resize array

short out_everyth(TokensDArray *stack, Token **TokensArray, int *len)

{

short r;

while((r=pop(&(*stack), &(*TokensArray),&(*len))) > 0);

return r;

}

//return 0 in case of success

// -1 in case of can not resize array

short out_UntilBrac(TokensDArray *stack, Token **TokensArray, int *len)

{

while((*stack).count > 0)

{

if((*stack).items[(*stack).count-1].ttype == tt_OPER)

if((*stack).items[(*stack).count-1].tvalue.otype == op_LBR)

{

(*stack).count--;

break;

}

if(pop(&(*stack), &(*TokensArray),&(*len)) < 0)

return -1;

}

return 0;

}

//For converting from infix form to postfix

//return 0 in case of success

// -1 unknown type of operator

// -2 unknown type of token

// -3 stack is over full

// -4 memory error: cant resize array

int infix2postfix(const Token *infix, int in_len, Token **postfix, int *out_len)

{

(*postfix)=(Token*)calloc(0,sizeof(Token));

TokensDArray stack = {NULL, 0};

stack.items=(Token*)calloc(0,sizeof(Token));

//go over all tokens of infix array

for(int CurInT=0; CurInT<in_len; CurInT++)

{

//identify type of current token

if(infix[CurInT].ttype == tt_OPER)

{

OperType OTinfix = infix[CurInT].tvalue.otype;

OperType OTstack = stack.items[stack.count-1].tvalue.otype;

switch(OTinfix)

{

case op_LBR:

if(push(&stack, &infix[CurInT])!= 0)

return -3;

break;

case op_RBR:

if(out_UntilBrac(&stack, &(*postfix),&(*out_len)) < 0)

return -4;

break;

default:

if(OTinfix == op_ADD || OTinfix == op_SUB)

{

while(OTstack == op_ADD || OTstack == op_SUB || OTstack == op_MUL || OTstack == op_DIV)

{

if(pop(&stack, &(*postfix),&(*out_len)) < 0)

return -4;

OTstack = stack.items[stack.count-1].tvalue.otype;

}

if(push(&stack, &infix[CurInT])!= 0)

return -3;

}

else if(OTinfix == op_MUL || OTinfix == op_DIV)

{

while(OTstack == op_MUL || OTstack == op_DIV)

{

if(pop(&stack, &(*postfix), &(*out_len)) < 0)

return -4;

OTstack = stack.items[stack.count-1].tvalue.otype;

}

if(push(&stack, &infix[CurInT])!= 0)

а return -3;

}

else

return -1;

break;

}

}

else if(infix[CurInT].ttype == tt_CONST || infix[CurInT].ttype == tt_ID)

{

Token* ptr2=realloc((*postfix),(++(*out_len))*sizeof(Token));

if(ptr2!= NULL)

(*postfix) = ptr2;

else

return -4;

(*postfix)[(*out_len)-1]=infix[CurInT];

}

else

return -2;

}

if(out_everyth(&stack, &(*postfix), &(*out_len)) < 0) //out all remained tokens of stack

return -4;

free(stack.items);

return 0;

}

Не нашли, что искали? Воспользуйтесь поиском: