VPF::Из инфиксной в постфиксную запись

Колесо

Дата 18.12.2011, 01:28 (ссылка)

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

Загрузка ...

Новичок

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

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

Здравствуйте. Нужно написать функцию перевода из инфиксной в постфиксную нотацию. Т.е. например, "5+4*2/1-4" записать как "5421/*+4-" Составил следующий код, но он почему то не делает то, что нужно. в чем ошибка?

Код


#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <windows.h>

int _tmain(int argc, _TCHAR* argv[])
{
    int j=0, k=0, prior[70];
    char stack[70];
    char st[255], outst[255];
            
    printf("Введите выражение: ");
    gets(st);

    for (int i = 0; i < strlen(st); i++)
    {
        if (st[i] >= '0' && st[i] <= '9')
        {
            outst[j] = st[i];
            j++;
            continue;
        }
        k++;
        switch (st[i])
        {
            case '+':
            {
                prior[k]=0;
                break;
            } 

            case '-':
            {
                prior[k]=0;
                break;
            } 

            case '/':
            {
                prior[k]=1;
                break;
            } 

            case '*':
            {
                prior[k]=1;
                break;
            } 
  
        }

        if (prior[k]>=prior[k-1])
        {
            stack[k]=st[i];
        }
        else 
        {
            for (int m=sizeof(stack); m<0; m--)
            {
                outst[j] = stack[m];
                stack[m]=0;
                j++;
            }
            stack[0]=st[i];

        }
    }
    printf("Ответ: %f", outst);
    system("pause");
 
    return 0;
}

Это сообщение отредактировал(а) Колесо - 18.12.2011, 09:21

rumit7

Дата 18.12.2011, 12:23 (ссылка)

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

Загрузка ...

Шустрый

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

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

Цитата(Колесо @ 18.12.2011, 01:28)

Ну вот, например здесь:

Код


for (int m=sizeof(stack); m<0; m--)

С чего Вы решили, что все 70 элементов из стека нужно вытаскивать?! И потом, на мой взгляд, лучше было бы не размазывать операции над стеком по всему коду, а оформить его как отдельную сущность. Например так:

Код


#include <stdio.h>
#include <string.h>
#include <assert.h>

typedef int bool_t;

typedef
struct stack
{
    char    stack_[70];
    size_t  top_;
    
} stack_t;

bool_t stack_empty(stack_t * stack)
{
    return stack->top_ == 0;
}

bool_t stack_full(stack_t * stack)
{
    return stack->top_ == sizeof(stack->stack_);
} 

void stack_push(stack_t * stack, char value)
{
    assert( !stack_full(stack) );
    
    stack->stack_[stack->top_] = value;
    stack->top_++;
}

void stack_pop(stack_t * stack)
{
    assert( !stack_empty(stack) );
    
    stack->top_--;
}

char stack_top(stack_t * stack)
{
    assert( !stack_empty(stack) );
    
    return stack->stack_[stack->top_-1];
}

bool_t is_operator(char ch)
{
    switch(ch)
    {
        case '+':
        case '-':
        case '*':
        case '/':
            return 1;
        default:
            return 0;
    }
}

size_t get_priority(char op)
{
    switch(op)
    {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        default:
            assert(0);
            return 0;
    }
}

int main()
{
    printf("Enter infix: ");
    
    char infix[256] = {0};      
    
    // cледует учесть, что нет способа ограничить число символов, которое прочитает функция gets(). 
    // Это означает, что массив, адресуемый указателем "statement", может переполниться. 
    // Следовательно, данная функция опасна по своей природе. 
    //
    gets(infix);
    
    char    postfix[256] = {0};
    size_t  j = 0;
    
    stack_t operators_stack = {0};              
    
    const size_t infix_length = strlen(infix);  // наверное лучше за пределами цикла, иначе "strlen" будет вызываться каждый раз
    for(size_t i = 0; i < infix_length; i++)
    {
        if( is_operator(infix[i]) )
        {
            while( !stack_empty(&operators_stack) 
                && get_priority(stack_top(&operators_stack)) >= get_priority(infix[i]) )
            {
                postfix[j++] = stack_top(&operators_stack);
                stack_pop(&operators_stack);
            
            }
            
            stack_push(&operators_stack, infix[i]);
        
        }else{
        
            postfix[j++] = infix[i];
        }
    }
    
    while( !stack_empty(&operators_stack) )
    {
        postfix[j++] = stack_top(&operators_stack);
        stack_pop(&operators_stack);
    }
    
    printf("Postfix is: %s", postfix);
 
    return 0;
}

Я так понял Вам нужно на Си, поэтому и ввел bool_t. На С++ все-же по другому пишут. Ну и код я много не тестил, и еще хорошо бы добавить поддержку операций "(", ")", унарный "+" и "-".

xvr

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

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

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

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

Код у вас весьма туманен и местами неправилен (в частности в строке 52 предполагается, что в стеке операция есть как минимум 2 операции, что для самой первой операции явно не так)
Погуглите по словам 'рекурсивный нисходящий парсер' (а лучше Recursive descent parser )

rumit7

Дата 19.12.2011, 20:27 (ссылка)

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

Загрузка ...

Шустрый

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

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

Цитата(xvr @ 19.12.2011, 15:15)

Как я понял, вот здесь объясняется очень даже ничего, плюс рабочий С++ код.

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