Задача: Преобразовать выражение ( т. е. текст специального вида), составленное из цифр и знаков четырех арифметических операций ( сложения, вычитания, умножения, деления) в постфиксную форму. В постфиксной форме сначала записываются операнды, а затем знак операции.
Тесты*:
| Инфиксная форма | Постфиксная форма | Инфиксная форма | Постфиксная форма |
| 3+4 | 3 4 + | 3+4*2/(1-5)^2 | 3 4 2 * 1 5 — 2 ^ / + |
| (5-4)+2 | 5 4 — 2 + | (1+2)*4+3 | 1 2 + 4 * 3 + |
| 2*(3+4)*5 | 2 3 4 + * 5 * | 78^6-3+9^(2-1) | 78 6 ^ 3 — 9 2 1 — ^ + |
*тесты взяты из примеров Абрамова, примеры из Википедии и немного собственных тестов.
Несколько оговорок по поводу программы:
1. Я расширил множество допустимых операторов добавив туда возведение в степень
2. Программа предполагает, что в выражении согласованы все скобки, иначе она будет работать не правильно.
3. В реализации программы через массив символов я предположил что вводимое выражение не будет превышать 50 символов. ( то есть, если учитывать пробелы, то финальная строка не будет превышать 100 символов)
4. Простите мне некоторое отклонение от привычного порядка отчета. Я считаю более удобным выложить сначала алгоритм, ибо он в обеих реализациях одинаков, а затем уже, показав код программы, комментировать детали каждой из реализаций.
Вообще постфиксная запись еще называется Обратной Польской Нотацией ( ОПН). За алгоритмом преобразования выражений из инфиксной ( привычной нам формы записи) в ОНП можно обратится к Википедии.
Алгоритм
- Пока есть ещё символы для чтения:
-
-
- Читаем очередной символ.
- Если символ является числом, добавляем его к выходной строке..
- Если символ является открывающей скобкой, помещаем его в стек.
- Если символ является закрывающей скобкой:
-
- До тех пор, пока верхним элементом стека не станет открывающая скобка, выталкиваем элементы из стека в выходную строку. При этом открывающая скобка удаляется из стека, но в выходную строку не добавляется. Если стек закончился раньше, чем мы встретили открывающую скобку, это означает, что в выражении либо неверно поставлен разделитель, либо не согласованы скобки.
- Если символ является оператором о1, тогда:
- 1) пока приоритет o1 меньше либо равен приоритету оператора, находящегося на вершине стека выталкиваем верхние элементы стека в выходную строку;
- 2) помещаем оператор o1 в стек.
-
- Когда входная строка закончилась, выталкиваем все символы из стека в выходную строку. В стеке должны были остаться только символы операторов; если это не так, значит в выражении не согласованы скобки.
Собственно весь код программы — это всего лишь последовательная реализация данного алгоритма, с учетом некоторых тонкостей.
Реализация через <string>
|
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 |
#include <iostream> #include <string> using namespace std; int main() { string str,stack; char word, word_last; while(cin>>word){ if((word>=48)&&(word<=57)){ //если символ это число if((word_last>=48)&&(word_last<=57)){ // Проверка, является ли предыдущий символ - числом str+=word; //Если да , то просто добавляем его, тем самым не разрушая число } else{ str+=' '; // В противном случае добавляем пробел и добавляем символ в главную строку str+=word; } } if(((word>=42)&&(word<=47))||(word==94)){ //если символ это операнд if(word=='*'){ //Замена умножения word='.'; } if(word=='-'){ //Замена минуса word=','; } if(stack.empty()){ // Если стэк пустой - то просто кладем символ в стэк stack+=word; } else{ // Если стэк не пуст if((stack.back()>=word)||(stack.back()==word-1)||(stack.back()==word+1)){ // Если верхний элемент стэка имеет больший приоритет while((stack.back()>=word)||(stack.back()==word-1)||(stack.back()==word+1)){ //выталкиваем все элементы из стэка str+=' '; //До тех пор, пока приоритет верхнего элемента не будет str+=stack.back(); //ниже входящего символа stack.pop_back(); } stack+=word; } else{ // если же верхний элемент ниже приоритетом - то просто кладем символ в стэк stack+=word; } } } if(word=='('){ //Если символ - открывающая скобка stack+=word; //добавляем ее в стэк } if(word==')'){ //Если встречающийся символ - закрывающая скобка while(stack.back()!='('){ // пока в стеке не встретится открывающая скобка str+=' '; // выталкиваем в главную строку все символы str+=stack.back(); stack.pop_back(); } stack.pop_back(); //Удаляем открывающую скобку из стека } word_last=word; //Присваиваем значение текущего символа для проверки в последующем цикле /*cout << "Numb:" << i++ << endl; // Распечатка пошаговых действий cout << "Word: |" << word << endl; cout <<"STR:| " << str <<"| SRA:|" << stack << endl;*/ } while(!stack.empty()){ //При окончании строки выталкиваем все символы из стека str+=' '; str+=stack.back(); stack.pop_back(); } for( int i=0; i<str.length();i++){ // Проходим циклом финальную строку для возврата требуемых символов if(str[i]=='.') str[i]='*'; if(str[i]==',') str[i]='-'; } cout <<"ИТОГ: ___ " << str << endl; return 0; } |
Моменты которые следовало бы объяснить:
1) Зачем мы проверяем, является ли предыдущий символ числом, если данный тоже число?
Эта проверка помогает нам определить, сколько цифр имело наше число. Без данной проверки, например, выражение: [latex]34*2-1[/latex] будет иметь вид не [latex]34 2 * 1 — [/latex] , а [latex]3 4 2 * 1 — [/latex]. В этом случае возникает двоякость при чтении выражения. Преобразовывая обратно можно предположить, что исходное выражение было [latex]3*42-1[/latex].
2) Зачем мы делаем замену символам умножения и вычитания, в случае когда читаемый символ это оператор?
Причина состоит в том, что нам требуется правильно контролировать приоритеты операций. Если распечатать номера символов то мы увидим следующее:
|
1 2 3 4 |
numb: 40 ( numb: 41 ) numb: 42 * numb: 43 + numb: 44 , numb: 45 - numb: 46 . numb: 47 / |
А по своему приоритету, операции сортируются так:
|
1 2 3 4 5 |
Приоритеты: • ^ высокий • * / средний • + - низкий • ( ) самый низкий |
Операция умножения по своему числу находится ниже плюса и минуса, хотя по приоритету она выше. И поэтому, гораздо проще заменить ее на точку, которая точно не встретится в математическом выражении, а закончив обработку, поменять обратно.
Менять минус на запятую мы вынуждены через то, что некоторые операции имеют попарно одинаковый приоритет. Мне показалось это выгодным вариантом, заменить минус запятой, и тем самым получить для каждой пары операций ( аддитивной и мультипликативной) своеобразный «радиус приоритета», который не пересекается с другим, таким же «радиусом». В финале, мы заменяем запятую на минус, так же, как и в случае с умножением и точкой.
Поскольку операция возведения в степень находится гораздо выше остальных, и не имеет пару в списке приоритетов ее изменения совсем не коснулись.
В общем, детали реализации состоят в том, что к строке stack мы обращаемся через функции, как к стеку символов. В общем — программа просто реализует описанный выше алгоритм.
Реализация через массив char
|
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 |
#include <iostream> #include <vector> using namespace std; int main() { char str[100]; //строку меняем на массив символов vector<char> stack; // строку меняем на вектор символов char word, word_last; int n=0, i=0; // переменные для помещения элементов в массив и пошаговой распечатки while(cin>>word){ if((word>=48)&&(word<=57)){ //если символ это число if((word_last>=48)&&(word_last<=57)){ // Проверка, является ли предыдущий символ - числом str[n++]=word; //Если да , то просто добавляем его, тем самым не разрушая число } else{ str[n++]=' '; // В противном случае добавляем пробел и добавляем символ в главную строку str[n++]=word; } } if(((word>=42)&&(word<=47))||(word==94)){ //если символ это операнд if(word=='*'){ //Замена умножения word='.'; } if(word=='-'){ //Замена минуса word=','; } if(stack.empty()){ // Если стэк пустой - то просто кладем символ в стэк stack.push_back(word); } else{ // Если стэк не пуст if((stack.back()>=word)||(stack.back()==word-1)||(stack.back()==word+1)){ while((stack.back()>=word)||(stack.back()==word-1)||(stack.back()==word+1)){ str[n++]=' '; // Если верхний элемент стэка имеет больший приоритет str[n++]=stack.back(); //выталкиваем все элементы из стэка stack.pop_back(); //lо тех пор, пока приоритет верхнего элемента не будет } //ниже входящего символа stack.push_back(word); } else{ // если же верхний элемент ниже приоритетом - то просто кладем символ в стэк stack.push_back(word); } } } if(word=='('){ //Если символ - открывающая скобка stack.push_back(word); //добавляем ее в стэк } if(word==')'){ //Если встречающийся символ - закрывающая скобка while(stack.back()!='('){ // пока в стэке не встретится открывающая скобка str[n++]=' '; // выталкиваем в главную строку все символы str[n++]=stack.back(); stack.pop_back(); } stack.pop_back(); //Удаляем открывающую скобку из стека } word_last=word; //Присваиваем значение текущего символа для проверки в последующем цикле //cout << "Numb:" << i++ << endl; // Распечатка пошаговых действий //cout << "Word: |" << word << endl; } while(!stack.empty()){ //При окончании строки выталкиваем все символы из стека str[n++]=' '; str[n++]=stack.back(); stack.pop_back(); } str[n]=''; int len=strlen(str); for( int i=0; str[i]!='';i++){ // Проходим циклом финальную строку для возврата требуемых символов if(str[i]=='.') str[i]='*'; if(str[i]==',') str[i]='-'; } cout <<"ИТОГ: ___ " << endl; for(int i=0; str[i]!=''; i++){ cout << str[i]; } cout << endl; return 0; } |
В общем, реализация не особо отличается от предыдущей. Алгоритм тот же, детали и идеи те же. Разница лишь в используемых инструментах. Теперь, вместо строки типа string мы используем массив символов. И как следствие, нам требуется ввести переменную ( в нашей программе — n) которая будет контролировать номер ячейки в которую будет присваиваться символ. Так же, после все обработки, требуется вставить дополнительно символ окончания строки ». После этого можно обращаться и форматировать строку, по нашей надобности.
Стэк здесь реализован через вектор символов. Тогда мы так же обращаемся к нему через функции, и при этом мы не должны контролировать его размерность, она динамически изменяется по ходу выполнения программы. Комментарии к данной реализации такие же как и в первой. Поэтому можно смело рассматривать две реализации, как отдельные и полноценные программы.
Зачтено