Форум программистов, компьютерный форум CyberForum.ru

Перевод выражения в обратную польскую запись - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.64
doomer74
1 / 1 / 0
Регистрация: 01.12.2011
Сообщений: 51
04.07.2012, 15:32     Перевод выражения в обратную польскую запись #1
Товарищи! Нужна помощь.
С помощью класса стек на основе динамического массива надо перевести инфиксное выражение в постфиксное с помощью алгоритма сортировочной станции. Входные данные должны быть в файле. Преподаватель посоветовал использовать для чтения строки из файла функцию fgets. Входные данные в виде строки, выходные так же должны быть в виде строки.

Помогите, пожалуйста, вот какой код я еле набросал, и то он работает с ошибками
Буду очень благодарен !

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
#include <iostream>
#include <conio.h>
#include <tchar.h>
#include <clocale>
#include <ctype.h>
#include <cstdlib>
#include <string>
#include <stdio.h>
#include <conio.h>
#define N 255
#define OK 1
#define NotOK 0
#define Op 5
using namespace std;
 
char opers[Op]={'+', '-', '*', '/', '('}; //  Массив операций, скобка сюда попала не случайно
int priors[Op]={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<Op; 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) //  является ли символ с оператором
{
    int i;
    for(i=0; i<Op; 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[N];
    char outexpr[N];
    char c;
    int i, j, x;
    i=0;
    j=0;
    Stack Poland;
    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])) // если символ закрывающаяся скобка
        { 
            Poland.pop(); 
            while(!IsOpBr(c)) // Пока верхним элементом не станет открывающаяся скобка вытлкиваем элементы из стека в выходную строку
            {
                outexpr[j]=c;
                Poland.pop();
                j++;
            }
        }
        if(IsOper(inexpr[i])&&inexpr[i]!='(')
        {
            outexpr[j]=' ';
            j++;
            x = Poland.pop();
            if(x==OK)
            {
                while(Prior(inexpr[i], c))
                {
                    outexpr[j]=c;
                    j++;
                    x = Poland.pop();
                    if(x==NotOK)
                        break;
                }
            }
            if(x!=NotOK)
                Poland.push(c);
            Poland.push(inexpr[i]);
        }
        i++;
    }
    while(Poland.pop()!=0)
        j++;
    outexpr[j]='\0';
    printf("%s", outexpr);
    _getch();
}
П.с. не обращайте на большое количество лишних директив препроцессора сверху, это я не успел убрать.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.07.2012, 15:32     Перевод выражения в обратную польскую запись
Посмотрите здесь:

цикл в обратную польскую запись C++
C++ Перевод инфиксного выражения в постфиксное (обратная польская запись)
C++ Строку в обратную польскую запись
C++ Как сосчитать обратную польскую?
C++ Запись выражения
C++ Перевод целочисленного выражения в double
C++ Программа, которая вычисляет польскую инверсную запись
C++ Запись выражения

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 12:24. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru