Блок-схема алгоритма
Листинг программы Файл 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;
}