VPF::Перевод инфиксного выражения в постфиксное (обратн

doomer74

Дата 4.7.2012, 19:54 (ссылка)

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

Загрузка ...

Новичок

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

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

Доброго времени суток!
Надо с помощью стека на динамическом массиве реализовать перевод инфиксного выражения в постфиксное. (обратная польская нотация). с помощью алгоритма сортировочной станции.

Кто не знает или забыл, что это такое, например:
дано выражение (4+5)*7
45+7* - это обратная польская запись (постфиксное выражение)

У меня почему-то не записываются все операции в стек, в чем ошибка в программе?

Код


#include <conio.h>
#include <stdio.h>
#include <iostream>
using namespace std;
 
char opers[5]={'+', '-', '*', '/', '('};
int priors[5]={1, 1, 2, 2, 0};
 
class Stack {
  private:
    char* arr; // Указатель на динамический массив с элементами стека
    char* top; // Указатель на верх стека
    int size; // Емкость стека
  public:
    Stack(int s = 10) 
    {  // Конструктор с одним параметром по умолчанию
       // Этот конструктор, в частности, заменяет и конструктор по умолчанию
        this->size = s;
        arr = new char[s];
        top = arr;
    }
    Stack(const Stack& s) 
    { // Копирующий конструктор
        this->size = s.size;
        this->arr = new char[s.size]; // Создаём НОВЫЙ динамический массив
        this->top = arr;
        char* p = s.arr; // Отдельный указатель на элементы старого массива
        while (p < s.top) 
    {
            *top++ = *p++; // Копируем элементы и позицию в новый массив
        }
    }
    
    bool isEmpty() 
    { // Метод проверяющий пуст ли стек
        if (top <= arr) {
            return true;
        } else {
            return false;
        }
    }
    
    bool isFull() 
    { // Метод проверяющий полон ли стек
        if (top - arr >= size) {
            return true;
        } else {
            return false;
        }
    }    
    
    void push(char val) 
    { // Метод добавляющий элемент в стек
        if(!isFull()) {
            *top = val;
            top++;
        } else {
            cout << "Stack full!" << endl; // Стэк полон
        }
    }
    
    char pop() 
    { // Метод извлекающий верхний элемент из стека
        if(!isEmpty()) 
            {
                    top--;
                    return *top;
            } 
    else 
            {
                    return 0; // Стэк пуст, вернём нуль
            }
    }
    
    void printStack() 
    { // Метод выводящий элементы стека в строку
        char* p = arr;
        while (p < top) 
        {
            cout << *p++ << ' ';
        }
        cout << endl;
    }
    
        ~Stack() 
    { // Деструктор
        delete[] arr; // Освобождает память от массива
    };
};
 
//===============================================================================================================
 
int Prior(char op1, char op2)
{
    int op1p, op2p, i;
    op1p=0;
    op2p=0;
    for (i=0; i< 5; i++)
    {
        if(op1==opers[i])
            op1p=i;
        if(op2==opers[i])
            op2p=i;
    }
    if(priors[op1p]<=priors[op2p])
        return 1;
    return 0;
}
 
int IsDigit(char c) // Если число
{
    if( (c>= '0') && (c<='9'))
        return 1;
    return 0;
}
int IsOper(char c) // Если операнд
{
    for(int i=0; i<5; i++)
    {
        if(c == opers[i])
            return 1;
    }
    return 0;
}
int IsOpBr(char c) // Если открывающая скобка
{
    if(c=='('||c=='['||c=='{')
        return 1;
    return 0;
}
int IsClBr(char c) // Если закрывающая скобка
{
    if(c==')'||c==']'||c=='}')
        return 1;
    return 0;
}
 
void main()
{
char inexpr[80];
char outexpr[80];
int k, point; // Счетчики 
Stack Poland; // Инициализация стека    
char c;
int i, j, x;
i=0;
j=0;
printf("Enter an expression\n");
scanf("%s", inexpr);
    while(inexpr[i]!='\0')
    {
        if(IsDigit(inexpr[i]))
        {
            outexpr[j]=inexpr[i];
            j++;
        }
        if(IsOpBr(inexpr[i]))
        {
            Poland.push(inexpr[i]);
        }
        if(IsClBr(inexpr[i]))
        {
            c = Poland.pop();
            while(!IsOpBr(c))
            {
                outexpr[j]=c;
                c = Poland.pop();
                j++;
            }
        }
        if(IsOper(inexpr[i]) && (inexpr[i]!='('))
        {
            outexpr[j]=' ';
            j++;
            x = c = Poland.pop();
            if (x == 1)
            {
                while (Prior(inexpr[i], c))
                {
                    outexpr[j]=c;
                    j++;
                    x = c = Poland.pop();
                    if (x == 0)
                        break;
                }
            }
            if( x!= 0)
                Poland.push(c);
            Poland.push(inexpr[i]);
        }
        i++;
    }
    while ( outexpr[j] == Poland.pop())
        j++;
    outexpr[j]='\0';
    printf("%s", outexpr);
    getch();
}

math64

Дата 5.7.2012, 08:06 (ссылка)

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

Загрузка ...

Эксперт

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

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

1. Ты делаешь pop() не проверив есть ли что на стеке.
2. Тебе нужен top() - проверить, что лежит вверху стека, не доставая его из стека. При отсутствии top() это делается при помощи pop(), но нужно не забыть после этого сделать push().

bsa

Дата 16.7.2012, 23:08 (ссылка)

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

Загрузка ...

Эксперт

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

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

но лучше иметь еще метод empty(), который будет возвращать true, если стек пуст. А top() (или front()) нужна не меньше, чем pop и push. Тем более, что в стандартном стеке (STL) метод pop не возвращает ничего.

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

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