Сразу говорю я не умею программировать на должном(вашем) уровне.Мне нужно реализовать перевод выражения из инфиксной в постфиксную форму (ВАЖНО:без STL контейнеров и т.п. Максимум пользовательский класс.). Опирался на 2 алгоритма:
1:
1. Читать очередной символ входной строки, пока не будет
достигнут конец выражения:
1.1. Если символ операнд, то он перемещается в
выходную строку.
1.2. Если символ операция и стек пуст, то он
проталкивается в стек.
1.3. Если символ операция и стек не пуст, а приоритет
символа операции меньше, чем у символа операции
вершины стека, то прочитанный символ проталкивается и
стек.
1.4. Если символ операция и стек не пуст, а приоритет
символа вершины стека, меньше приоритета входного
символа, то из стека в выходную строку выталкиваются
все символы операций с меньшим или равным
приоритету входного символа, после чего входной
символ операции заносится в стек.
1.5. Если входной символ левая открывающая скобка, то
она проталкивается в стек.
1.6. Если входной символ правая закрывающая скобка, то
она выталкивает из стека в выходную строку все символы
до левой открывающей скобки. сами скобки
уничтожаются и в выходную строку не попадают.
1.7. Если входной символ - маркер конца строки, то из
стека в выходную строку выталкиваются все символы.
2. Результат выходной строки. Конец алгоритма.
2:
1.Константы и переменные кладутся в формируемую запись в порядке их появления в исходном массиве.
2.При появлении операции в исходном массиве:
a.если в стеке нет операций или верхним элементом стека является открывающая скобка, операции кладётся в стек;
b.если новая операции имеет больший* приоритет, чем верхняя операции в стеке, то новая операции кладётся в стек;
c.если новая операция имеет меньший или равный приоритет, чем верхняя операции в стеке, то операции, находящиеся в
стеке, до ближайшей открывающей скобки или до операции с приоритетом меньшим, чем у новой операции,
перекладываются в формируемую запись, а новая операции кладётся в стек.
3.Открывающая скобка кладётся в стек.
4.Закрывающая скобка выталкивает из стека в формируемую запись все операции до ближайшей открывающей скобки,
открывающая скобка удаляется из стека.
5.После того, как мы добрались до конца исходного выражения, операции, оставшиеся в стеке, перекладываются в
формируемое выражение.
Если можете посоветовать какую-нибудь вразумительную лит-ру буду благодарен.
P.S. Не нужно отсылать меня искать по темам форума(пересмотрел более 10 тем не нашёл решения, к сожалению)
P.S.S. Надеюсь на понимание и помощь. Заранее спасибо.Код ниже.
| 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
194
195
196
197
198
199
200
201
202
| #include <iostream>
#include <stdio.h>
#include <fstream>
#include <string.h>
#include <Windows.h>
using std::ifstream;
using std::ofstream;
using std::cout;
using std::cin;
using std::ios;
using std::ostream;
using std::istream;
using std::endl;
void push(char a);
int pop();
char show_element(int a);
int top();
void topdel();
bool empty();
int show_prior(char a);
void ops(char *inp);
void work(istream &in, ostream &out);
bool opel(char inp);
int tos = 0;
char stack[30];
int max = 30;
char opz[50];
ifstream In("In.txt");
ofstream Out("Out.txt", ios::out);
int main()
{
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
work(In,Out);
return 0;
}
void work(istream &in, ostream &out)
{
char inp[50];
if (!in)
{
cout << "Файл не открылся" << endl;
return;
}
in.getline(inp, 50);
char *Out;
ops(inp);
Out = opz;
out << Out << endl;
}
bool opel(char inp)
{
if (inp == '+' || inp == '-' || inp == '/' || inp == '^' || inp == '*' || inp == '(' || inp == ')')
return false;
else
return true;
}
void ops(char *inp)
{
int i = 0;
int j = 0;
while (inp[i] != '\0')
{
if (opel(inp[i]))
{
opz[j] = inp[i];
j++;
i++;
}
else
{
if (empty() || show_prior(show_element(top())) == 0)
{
push(inp[i]);
i++;
}
if (!empty() && show_prior(inp[i]) < show_prior(show_element(top())))
{
push(inp[i]);
i++;
}
if (!empty() && show_prior(inp[i]) >= show_prior(show_element(top())))
{
while (1)
{
if (show_prior(inp[i]) >= show_prior(show_element(top())) || show_prior(inp[i]) == 0)
{
break;
}
else
{
opz[j] = pop();
j++;
}
}
push(inp[i]);
i++;
}
if (show_prior(inp[i]) == 0)
{
push(inp[i]);
i++;
}
if (show_prior(inp[i]) == 1)
{
while (1)
{
if (show_element(top()) == '(')
{
topdel();
i++;
break;
}
else
{
opz[j] = pop();
j++;
}
}
}
}
}
if (!empty())
{
while (!empty())
{
opz[j] = pop();
j++;
}
}
}
int show_prior(char a)
{
return
a == '(' ? 0 :
a == ')' ? 1 :
a == '+' || a == '-' ? 2 :
a == '*' || a == '/' ? 3 :
4;
}
void push(char a)
{
if (tos == max)
return;
stack[tos] = a;
tos++;
}
int pop()
{
if (tos>=0)
{
tos--;
return stack[tos];
}
}
int top()
{
return tos;
}
char show_element(int a)
{
return stack[a];
}
void topdel()
{
tos--;
}
bool empty()
{
if (tos == 0)
return true;
else
return false;
} |
|
Забыл упомянуть в этом коде при входных данных:a+b-c+d/(f-g*h)+z
результатом получается выражение:afh*g-(z+d+c-b+
а должно быть:ab+c-dfgh*-/+z+.
Добавлено через 14 часов 58 минут
Всё нашёл для себя решение тему можно закрыть если кого интересует моя реализация , то код будет ниже. Возможно банально и коряво зато (как говорится) сам и правильно. Лично у меня всё встало на места. Всем добра!
| 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
| #include <iostream>
#include <stdio.h>
#include <fstream>
#include <string.h>
#include <Windows.h>
using std::ifstream;
using std::ofstream;
using std::cout;
using std::cin;
using std::ios;
using std::ostream;
using std::istream;
using std::endl;
int pop();
void push(char a);
char show_element(int a);
int top();
void topdel();
bool empty();
int show_sit(char a,char b);
void ops(char *inp);
void work(istream &in, ostream &out);
bool opel(char inp);
int stack[30];
int tos = 0;
int max = 30;
char opz[256];
ifstream In("In.txt");
ofstream Out("Out.txt", ios::out);
int main()
{
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
work(In,Out);
return 0;
}
void work(istream &in, ostream &out)
{
char inp[256];
if (!in)
{
cout << "Файл не открылся" << endl;
return;
}
in.getline(inp, 256);
char *Out;
ops(inp);
Out = opz;
out << Out << endl;
}
bool opel(char inp)
{
return (inp == '+' || inp == '-' || inp == '/' || inp == '^' || inp == '*' || inp == '(' || inp == ')' || inp == '\0') ? false : true;
}
void ops(char *inp)
{
int i = 0;
int j = 0;
while (i<=strlen(inp))
{
if (opel(inp[i]))
{
opz[j] = inp[i];
j++;
i++;
}
else
{
if (empty())
{
push(inp[i]);
i++;
}
else
{
switch (show_sit(inp[i], show_element(top()-1)))
{
case 0:
{
cout << "Не предусмотренная ситуация!" << endl;
return;
}break;
case 1:
{
push(inp[i]);
i++;
}break;
case 2:
{
opz[j] = pop();
j++;
}break;
case 3:
{
topdel();
i++;
}break;
case 4:
{
if (!empty())
{
while (!empty())
{
opz[j] = pop();
j++;
}
}
return;
}break;
case 5:
{
cout << "Выражение составлено некорректно!" << endl;
return;
}break;
}
}
}
}
}
int pop()
{
if (tos >= 0)
{
tos--;
return stack[tos];
}
}
void push(char a)
{
if (tos == max)
return;
stack[tos] = a;
tos++;
}
char show_element(int a)
{
return stack[a];
}
int top()
{
return tos;
}
void topdel()
{
tos--;
}
bool empty()
{
return (tos == 0) ? true : false;
}
int show_sit(char a, char b)
{
return
(a == '\0'&& b == '\0') ? 4 :
(a == '\0'&&b == '(') || (a == ')'&& b == '\0') ? 5 :
(a == ')'&& b == '(') ? 3 :
(a == '\0'&&b == '+' || a == '\0'&&b == '-' || a == '\0'&&b == '*' || a == '\0'&&b == '/' || a == '\0'&&b == '^' ||
a == '+'&&b == '+' || a == '+'&&b == '-' || a == '+'&&b == '*' || a == '+'&&b == '/' || a == '+'&&b == '^' ||
a == '-'&&b == '+' || a == '-'&&b == '-' || a == '-'&&b == '*' || a == '-'&&b == '/' || a == '-'&&b == '^' ||
a == '*'&&b == '*' || a == '*'&&b == '/' || a == '*'&&b == '^' ||
a == '/'&&b == '*' || a == '/'&&b == '/' || a == '/'&&b == '^' ||
a == '^'&&b == '^' ||
a == ')'&&b == '+' || a == ')'&&b == '-' || a == ')'&&b == '*' || a == ')'&&b == '/' || a == ')'&&b == '^') ? 2 :
(a == '+'&&b == '\0' ||
a == '-'&&b == '\0' ||
a == '*'&&b == '\0' || a == '*'&&b == '+' || a == '*'&&b == '-' ||
a == '/'&&b == '\0' || a == '/'&&b == '+' || a == '/'&&b == '-' ||
a == '^'&&b == '\0' || a == '^'&&b == '+' || a == '^'&&b == '-' || a == '^'&&b == '*' || a == '^'&&b == '/' ||
a == '('&&b == '\0' || a == '('&&b == '+' || a == '('&&b == '-' || a == '('&&b == '*' || a == '('&&b == '/' || a == '('&&b == '^' || a == '('&&b == ')' ||
b == '('&&a == '+' || b == '('&&a == '-' || b == '('&&a == '*' || b == '('&&a == '/' || b == '('&&a == '^' || b == '('&&a == '(') ? 1 :
0;
} |
|
(
