VPF::Рекурсивное вычесление Prefix с помощью fork()

56illusion

Дата 25.11.2013, 15:55 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 52
Регистрация: 12.5.2010

Репутация: нет
Всего: нет

Курс: Операционные системы.
Задача:
Реализовать рекурсию с использованием Форков для вычисления Prefix выражений. Каждый рекурсивный вызов обрабатываеться в отдельном Форке.
В качестве примера данно выражение: (+(+(+38)5)(*(-86)3))
Прошу помочь с этой задачяй или подкинуть идею решения.
часов 10 тремя разными алгоритмами писал код но не одно из решений не работало.
Ни кто из однокурсников пока решить не смог smile

)) Спасибо.

baldina

Дата 25.11.2013, 16:32 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 1
Всего: 101

покажите упомянутые алгоритмы. в чем именно затруднения?

56illusion

Дата 25.11.2013, 17:00 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 52
Регистрация: 12.5.2010

Репутация: нет
Всего: нет

в условиях решения задачи нужно использовать pipe ךдля контакта и передачи инфы между форками.
в коде есть ошибки связанные с поинтерами, поетому если что то странное увидите, не обращайте внимания.
Вопрос в том правильно ли написанна логика?! יраньше мне не приходилось писать рекурсию с форками smile

Код


#define READ 0
#define WRITE 1
#define IOERROR 2
#define MAX_SIZE 50

const char DIGITS[] = "1234567890";
const char OPERANDS[] = "+-*/";
const char SPACE = ' ';

char msg[] = "Enter prefix expression\n";
int expression_size;
char prefix[MAX_SIZE];
size_t bytes_read;
char *token[2];

int fd[2];
int left_number, right_number;
    
int pid;
int tmp_indexA, tmp_indexB;
int i, j, indexx;
int operand_res;
char *tmp_exp;

void parseToken(char*, char*[2]);
void calcPrefix(char*);

int main(int argc, char **argv)
{
    
    // write msg for user
    write(WRITE, msg, sizeof(msg));
    
    // read user inpute
    bytes_read = read(READ, &prefix, sizeof(prefix)); 
    expression_size = bytes_read/sizeof(char);
    
    calcPrefix(prefix);
    return 1;
}

// Делит стринг token на двое (two substrings for left & right forked sons)
// (+(+23)3) ==> buffer[0] = "+23)" | buffer[1] = "3)"
void parseToken(char *token, char *buffer[2])
{
    tmp_indexA = 1;
    tmp_indexB = 1;
    indexx = 0;
    j = 0;
    
    for(i = 1; i < strlen(token)-1; i++)
    {
        if(token[i] == '(') indexx++;
        else if(token[i] == ')')
        {
             indexx--;
             if(indexx == 0) 
             {
                 strncpy(token, buffer[j++], (tmp_indexB-tmp_indexA)*sizeof(char));
                 tmp_indexA = tmp_indexB + 1;
             }     
        }
        tmp_indexB++;
    }
}

void calcPrefix(char *expression)
{
    
    if(strlen(expression) == 1 && strstr(DIGITS, expression))
    {
        close(fd[READ]);
        write(fd[WRITE], (int*)atoi(expression), sizeof(int));
        close(fd[WRITE]);
        exit(1);
    }
    else
    {
                // идти по массиву пока не встретим операнд, после операнда делим выражения на двое
        while(!strstr(OPERANDS, &expression[0]))
        {
             expression++;
             printf("char %c\n", expression[0]);
        }
        strncpy(expression, tmp_exp, strlen(expression)*sizeof(char));
        //printf("sub expression %s\n", tmp_exp);
        parseToken(tmp_exp, token);    
        
        pipe(fd);
        
        // left recursion
        switch(pid = fork())
        {
            case -1:
              perror("Error\n");
              exit(1);
            case 0:
              printf("son pid = [%d]\n", getpid());
              calcPrefix(token[0]);
              break;
            default:
              while(wait(NULL) > 0);
              close(fd[WRITE]);
              read(fd[READ], &left_number, sizeof(int)); 
              close(fd[READ]);
              switch(pid = fork())
              {
                  case -1:
                     perror("fork error\n");
                     break;
                  case 0:
                     printf("son pid = [%d]\n", getpid());
                     calcPrefix(token[1]);
                     break;
                  default:
                     while(wait(NULL) > 0);
                     close(fd[WRITE]);
                     read(fd[READ], &right_number, sizeof(int));
                     close(fd[READ]);
                     
                     printf("left number ==> %d\n", left_number);
                     printf("right number ==> %d\n", right_number);
            
                     switch(expression[0])
                     {
                      case '+':
                          operand_res = left_number + right_number;
                          break;
                        case '-':
                           operand_res = left_number - right_number;
                           break;
                        case '*':
                           operand_res = left_number * right_number;
                           break;
                        case '/':
                           operand_res = left_number / right_number;
                           break;
                        default:
                           break;
                    }
                    
                     printf("result ==> %d ", operand_res);
                     break;
              }
              break;          
        }
        // right recursion
    }
}

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Программирование под Unix/Linux \| Следующая тема »