ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.01.2025
Просмотров: 274
Скачиваний: 2
Блок-схема алгоритма
Листинг программы Файл 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;
}
Файл infix2postfix.H
#ifndef INFIX2POSTFIX_H
#define INFIX2POSTFIX_H
/* типы лексем: константы, операции, имена переменных */
typedef enum { tt_CONST, tt_OPER, tt_ID } TokenType;
/* виды операций: сложение, вычитание, умножение, деление,
* левая и правая скобки */
typedef enum {op_ADD='+', op_SUB='-', op_MUL='*', op_DIV='/', op_LBR='(', op_RBR=')'} OperType;
/* максимальная длина имени переменной */
#define MAX_ID_LEN 40
/* тип - лексема */
typedef struct {
TokenType ttype;
union Value {
/* с лексемой связано одно из следующих значений */
int inum;
OperType otype;
char id[MAX_ID_LEN + 1];
} tvalue;
int num;
} Token;
//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);
//For converting from infix form to postfix
//return 0 in case of success
// -1 unknow type of operator
// -2 unknow 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);
#endif
Файл unit_tests.C
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include "infix2postfix.h"
#define IN_STR_SIZE 200
char strC[IN_STR_SIZE] = "";
void out_TokensArray(Token **t_array, int *len)
{
memset(strC,0,sizeof(strC)); //erase strC
char strT[IN_STR_SIZE] = "";
for(int i=0; i<(*len); i++)
switch((*t_array)[i].ttype)
{
case tt_CONST:
printf("%d ", (*t_array)[i].tvalue.inum);
sprintf(strT, "%d ", (*t_array)[i].tvalue.inum);
strcat(strC, strT);
break;
case tt_OPER:
printf("%c ", (*t_array)[i].tvalue.otype);
sprintf(strT, "%c ", (*t_array)[i].tvalue.otype);
strcat(strC, strT);
break;
case tt_ID:
printf("%s ", (*t_array)[i].tvalue.id);
sprintf(strT, "%s ", (*t_array)[i].tvalue.id);
strcat(strC, strT);
break;
}
printf("\n");
}
void covert_i2p(const char *s)
{
printf(" ORIGINAL INPUTED STRING: \"%s\"", s);
Token *infix;
int in_len = 0;
switch(tokenize(s, &infix, &in_len))
{
case 0:
printf("\n INFIX: ");
out_TokensArray(&infix, &in_len);
Token *postfix;
int out_len = 0;
switch(infix2postfix(infix, in_len, &postfix, &out_len))
{
case 0:
printf(" POSTFIX: ");
out_TokensArray(&postfix, &out_len);
break;
case -1:
printf("\nError: Unkown type of operator\n");
strcpy(strC, "Error");
break;
case -2:
printf("\nError: Unkown type of token\n");
strcpy(strC, "Error");
break;
case -3:
printf("\nError: Memory error: Stack is over full\n");
strcpy(strC, "Error");
break;
case -4:
printf("\nError: Memory error: Cant resize array\n");
strcpy(strC, "Error");
break;
default:
printf("\nError: Unknown error\n");
strcpy(strC, "Error");
break;
}
free(postfix);
break;
case -1:
printf("\nError: Format of token is incorrect\n");
strcpy(strC, "Error");
break;
case -2:
printf("\nError: Memory error: Cant resize array\n");
strcpy(strC, "Error");
break;
default:
printf("\nError: Unknown error\n");
strcpy(strC, "Error");
break;
}
free(infix);
}
void test(char *headline, char *in_str, char *expect_str)
{
printf("\n%s\n", headline);
covert_i2p(in_str);
printf(" EXPECTED: %s\n", expect_str);
if(strcmp(strC, expect_str) == 0)
printf(" PASSED");
else
printf(" DONT MATCH!!!");
printf("\nNext... press <Enter>\n");
getchar();
}
int main(int argc, char* argv[])
{
printf("\nUnit tests for infix2postfix.h is run\n");
printf(" Press <Enter> for the full test script...\n");
printf(" Input string and press <Enter> if you want to do test with this string...\n");
char s[IN_STR_SIZE];
gets(s);
if(strlen(s) == 0)
{
printf("Test script is running...\n");
//test("", "", " ");
test("Does it understand correct tokens?", "2 + 123 - ( abc * abc123 ) / a1b2c3", "2 123 + abc abc123 * a1b2c3 / - ");
test("Will it be worked correct with spaces/tabs at the begin/end?", " 2 + 7 ", "2 7 + ");
test("Can it work with one token?", "7", "7 ");
test("Will it return error in case of wrong format of token?", "a + 987bcd", "Error");
test("Will it return error in case of unknown operator?", "5 ^ 9", "Error");
test("Some random test 1", "3 + 4 * 2 / ( 1 - 5 )", "3 4 2 * 1 5 - / + ");
test("Some random test 2", "( 1 + 23 * 4 ) * ( 5 - 1 )", "1 23 4 * + 5 1 - * ");
test("Some random test 3", "7 + ( 5 - 2 ) * 4", "7 5 2 - 4 * + ");
test("Some random test 4", "8 / ( 2 + 2 )", "8 2 2 + / ");
test("Some random test 5", "( 8 / ( 2 + 2 ) )", "8 2 2 + / ");
printf("Test script is over\n");
}
else
covert_i2p(s);
printf("\nPress <Enter> for exit");
getchar();
return 0;
}