Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.64
doomer74
1 / 1 / 0
Регистрация: 01.12.2011
Сообщений: 51
#1

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

04.07.2012, 15:32. Просмотров 1807. Ответов 0
Метки нет (Все метки)

Товарищи! Нужна помощь.
С помощью класса стек на основе динамического массива надо перевести инфиксное выражение в постфиксное с помощью алгоритма сортировочной станции. Входные данные должны быть в файле. Преподаватель посоветовал использовать для чтения строки из файла функцию 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();
}
П.с. не обращайте на большое количество лишних директив препроцессора сверху, это я не успел убрать.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.07.2012, 15:32
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Перевод выражения в обратную польскую запись (C++):

Перевод в обратную польскую нотацию - C++
Добрый вечер. Для реализации некоей сложной (на мой взгляд) программы понадобился перевод в обратную польскую запись. Итак, даны 2 строки ...

цикл в обратную польскую запись - C++
Смысл такой - на входе есть файл,где записан цикл.Программа должна преобразовать запись в обратную польску и записать в файл. Помогите...

Строку в обратную польскую запись - C++
Подскажите, как представить выражение из строки в обратную польскую запись и потом посчитать? Наверное есть уже готовые алгоритмы...

Как сосчитать обратную польскую? - C++
#include &lt;stdio.h&gt; #include &lt;conio.h&gt; #define N 255 #define OK 1 #define NotOK 0 #define Op 5 char Stack; char opers={'+',...

Перевод инфиксного выражения в постфиксное (обратная польская запись) - C++
Всем привет! Надо с помощью стека на динамическом массиве реализовать перевод инфиксного выражения в постфиксное. (обратная польская...

Программа, которая вычисляет польскую инверсную запись - C++
Программа которая вычисляет польскую инверсную запись

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.07.2012, 15:32
Привет! Вот еще темы с ответами:

Перевод целочисленного выражения в double - C++
Собственно ситуация следующая: class A{ private: int a,b,c; public: //---код----// operator double() { return...

Перевод из инфиксной в постфиксную запись - C++
Суть моей программы: перевод из инфиксной в постфиксную запись. Но проблема в том, что функция типа string не возвращает значение. В чём...

Перевод математической записи в запись на С++ - C++
Вроди как записал но ответ не совпадает записать но ответ не совпадает :( ...

Запись выражения - C++
Помогите пожалуйста записать следующее выражение. Безуспешная попытка: f=(A*B) / (C)+sin(C) + log(log(A)) / sin(B) - sqrt(pow(A, 3) -...


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

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.