С Новым годом! Форум программистов, компьютерный форум, киберфорум
Алгоритмы
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.92/96: Рейтинг темы: голосов - 96, средняя оценка - 4.92
1 / 1 / 0
Регистрация: 25.01.2010
Сообщений: 4

Перевод префиксной формы записи в постфиксную

25.01.2010, 19:41. Показов 18362. Ответов 14
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Помогите пожалуйста написать алгоритм перевода из префиксной формы записи в постфиксную(минуя инфиксную).
В сети таких алгоритмов не нашел. Для перевода из инфиксной в постфиксную сколько угодно, а такого нет.
Для небольших выражений написал, а вот универсальный алгоритм составить ни как не могу.

Вот например для такого выражения:
/*+ab-cd-+def

Надо получить: ab+cd-*de+f-/

НО КАК?
0
Лучшие ответы (1)
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
25.01.2010, 19:41
Ответы с готовыми решениями:

Перевод из инфиксной записи в постфиксную (С++).С применением рекурсии,как это реализовать?
Перевод из инфиксной записи в постфиксную (С++).С помощью рекурсии,как это реализовать? Например ((5+6)*2)/2 это 56+2*2/ в постфиксной...

Преобразование формы записи выражения из префиксной в постфиксную
Требуеться написать программу на языке Prolog "Преобразование формы записи выражения из префиксной в постфиксную". Очень срочно...

Перевод формулы из префиксной формы в инфиксную
Надо перевести формулу из префиксной формы записи в инфиксную т.е. дано на входе -+*abz*cz сделать (a+b)*z-c*z, вроде делается через...

14
Day
 Аватар для Day
1180 / 990 / 83
Регистрация: 29.10.2009
Сообщений: 1,385
26.01.2010, 01:11
Счетчик = 0
Пока строка не кончилась
{
Операция - в стек ее.
Переменная - в строку и счетчик ++
Ежели счетчик >= 2, вынимаем операцию из стека - в строку ее, и счетчик -= 2
}
Кажется так, но уверенности нет
0
1 / 1 / 0
Регистрация: 25.01.2010
Сообщений: 4
26.01.2010, 17:05  [ТС]
Цитата Сообщение от Day Посмотреть сообщение
Счетчик = 0
Пока строка не кончилась
{
Операция - в стек ее.
Переменная - в строку и счетчик ++
Ежели счетчик >= 2, вынимаем операцию из стека - в строку ее, и счетчик -= 2
}
Кажется так, но уверенности нет
Это возможно только для того случая когда в качестве операнда выступает переменная, а если выражение, то этот метод не работает.
А вот для строки
/*+ab-cd+-def
уже не работает.
0
Day
 Аватар для Day
1180 / 990 / 83
Регистрация: 29.10.2009
Сообщений: 1,385
27.01.2010, 12:41
Лучший ответ Сообщение было отмечено как решение

Решение

Donizetti, правда твоя.
Подумать надоть

Добавлено через 15 часов 12 минут
Предлагаю такой алгоритм (тоже без уверенности, но на предложенном
примере он работает)

Как только встречается конструкция ОПП, заменяем ее на (ППО) и это
считаем тоже переменной.
Начинаем все сначала, пока не останется одна "переменная"
(наверное, с самого начала можно не начинать)
Потом убираем все скобки - и все!
О - операция
П - переменная

/*+ab-cd-+def
/*(ab+)-cd-+def
/*(ab+)(cd-)-+def
/((ab+)(cd-)*)-+def
/((ab+)(cd-)*)-(de+)f
/((ab+)(cd-)*)((de+)f-)
(((ab+)(cd-)*)((de+)f-)/)
ab+cd-*de+f-/

А вообще, если погуглить "префиксная постфиксная", то четвертая
найденная ссылка на zaplaty.ru чего-то предлагает за небольшие денежки
3
1 / 1 / 0
Регистрация: 25.01.2010
Сообщений: 4
28.01.2010, 20:02  [ТС]
Спасибо. Вроде всё правильно.
0
Day
 Аватар для Day
1180 / 990 / 83
Регистрация: 29.10.2009
Сообщений: 1,385
28.01.2010, 20:37
Конечно, внутренние скобки можно удалять сразу.
Т.е. у нас есть 2 вида "переменных" (термин неудачный) ::=
просто переменная | (постфиксное выражение)

Это я так, чтоб самому себе прояснить
1
1 / 1 / 0
Регистрация: 25.01.2010
Сообщений: 4
29.01.2010, 18:25  [ТС]
Один мой знакомый предложил заменять выражение в скобках на другой символ, например из таблица ASCII, т.е. встретили первое такое выражение заменили на на символ с кодом 1, второе на символ с кодом 2 и.т.д.
Потом заменяем эти символы наоборот на выражения, тока преобразованные из префиксной в поствиксную форму.
Т.е.

*+ab-cd
*12
3

1=ab+
2=cd-
3=12*

3
12*
ab+cd-*

Добавлено через 8 минут
Вот собственно код:

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
#include "stdafx.h"
#include <iostream> 
#include <windows.h> 
 
using namespace std;
 
const int BUF_SIZE = 255; 
 
void printCyr (char []);
bool checkCh (char c);
void delCh (char [], int);
void insCh (char c[], char ch, int n);
 
 
int main(int argc, char* argv[])
{
 
    char str[BUF_SIZE];
        
    printCyr ("Введите выражение:");
    cin>>str;
 
    int length = strlen(str);
    int countOperand = 0;
    int countOperation = 0;
 
    for (int i=0;i<length;i++)
        if (checkCh(str[i])) countOperation++;
        else countOperand++;
        if (!(countOperand == countOperation+1))
        {
            printCyr("Ошибка в выражении!");
            system("pause");
            return 1;
        }
 
    char temp[BUF_SIZE][3];
    int beginLen = length;
    int k=1;
 
    while (length>2)
    {   
        if (!checkCh(str[0]))
        {
            printCyr("Ошибка в выражении!");
            system("pause");
            return 1;
        }
        for (int i=0;i<length;i++)
            if (checkCh(str[i]) && !checkCh(str[i+1]) && !checkCh(str[i+2]))
            {
                temp[k][0]=str[i+1];
                temp[k][1]=str[i+2];
                temp[k][2]=str[i];
                str[i]=k;
                delCh(str, i+2);
                delCh(str, i+1);
                length-=2;
                k++;
            }
    }
 
    while (length!=beginLen)
        for (int i=0;i<length;i++)
            for (int j=1;j<k;j++)
                if (str[i]==j)
                {
                    str[i]=temp[j][0];
                    insCh(str,temp[j][1],i);
                    insCh(str,temp[j][2],i+1);
                    length+=2;
                }
 
    cout<<str<<endl;
    system("pause");
 
    return 0;
}
 
void printCyr (char message[])
{
    char buf[255];
    CharToOemA (message, buf);
    cout<<buf<<endl;
}
 
bool checkCh (char c)
{
    if ((c=='+') || (c=='-') || (c=='*') || (c=='/'))
        return true;
    return false;
}
 
void delCh (char c[], int n)
{
    int length = strlen(c);
    for (int i = n;i<length-1;i++)
    {
        c[i] = c[i+1];
    }
    c[length-1] = '\0';
}
 
void insCh (char c[], char ch, int n)
{
    int length = strlen(c);
    for (int i = length;i>n;i--)
            c[i+1] = c[i];
    c[n+1]=ch;
    c[length+1] = '\0';
}
1
54 / 1 / 1
Регистрация: 03.06.2011
Сообщений: 48
10.10.2011, 16:35
Pascal
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
program izprefiks;
const N=50;
type  TS=array[1..N] of char;
var
 ST:TS;
 str,str2:string;
 k1,k2,i,j,sp:integer;
 
procedure PUSH(var R:TS;var uk:integer;x:char);
begin
  uk:=uk+1;
  if uk>N then  begin writeln('perepolnenie');readln; exit;  end
     else R[uk]:=x;
end;
 
function POP(var R:TS;var uk:integer):char;
begin
  if uk=0 then  begin writeln('stek pust');readln; exit;  end
     else begin POP:=R[uk]; uk:=uk-1;   end
end;
 
function znak(ch:char):boolean;
begin
 if (ch='+') or (ch='-') or (ch='*') or (ch='/')
   then znak:=true
   else znak:=false;
end;
 
 
begin
j:=0;sp:=0;k1:=0;
str:='/*+ab-cd-+def';
 
 for i:=1 to length(str) do begin
 
  if k1=2 then begin
             j:=j+1;
             {str2[j]:=pop(ST,sp)} write(pop(ST,sp));
             k1:=0;
             k2:=k2+1;
  end;
  if k2=2 then begin
             j:=j+1;
             {str2[j]:=pop(ST,sp)} write(pop(ST,sp));
             k2:=0;
  end;
 
  if znak(str[i]) then push(ST,sp,str[i])
                  else begin
                   j:=j+1;
                   {str2[j]:=str[i];}write(str[i]);
                   k1:=k1+1;
                  end;
 
 end;
 while sp<>0 do write(pop(ST,sp));
 writeln;
 
end.
Алгоритм плохой но всё же /*+ab-cd-+def решает)
0
Эксперт С++
 Аватар для Mr.X
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
11.10.2011, 11:36
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
/////////////////////////////////////////////////////////////////////////////////////////
//Перевод из префиксной формы записи в постфиксную (минуя инфиксную).
/////////////////////////////////////////////////////////////////////////////////////////
#include <cctype>
#include <iostream>
#include <string>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string  T_str;
/////////////////////////////////////////////////////////////////////////////////////////
T_str  pref_to_postf(T_str&  s)
{   
    T_str  res = s.substr(0, 1);
    s.erase(0, 1);
 
    if( !isalpha( res[0] ) )
    {
        T_str  arg_A = pref_to_postf(s);
        T_str  arg_B = pref_to_postf(s);
        res = arg_A + arg_B + res;
    }
    return  res;
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    std::cout << "Введите выражение в префиксной форме:"
              << std::endl;
    T_str  s;
    std::cin >> s;
 
    std::cout << "Это же выражение в постфиксной форме:"
              << std::endl
              << pref_to_postf(s)
              << std::endl;
}
2
54 / 1 / 1
Регистрация: 03.06.2011
Сообщений: 48
12.10.2011, 15:11
Mr.X, а если словесно алгоритм это как?, ото я в си слабоват.
0
Эксперт С++
 Аватар для Mr.X
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
12.10.2011, 15:28
Цитата Сообщение от pasha0409 Посмотреть сообщение
Mr.X, а если словесно алгоритм это как?, ото я в си слабоват.
Ну, функцпя pref_to_postf делает следующее:
1. Откусывает от строки первый символ.
2. Если это не операция, то возвращает его.
3. Если же это операция, то получает первый и второй ее аргументы в постфиксной форме, дважды применив к строке функцию pref_to_postf.
4. Возвращает конкантенацию первого и второго аргументов, а также откушенного знака операции.
1
0 / 0 / 0
Регистрация: 26.11.2014
Сообщений: 12
31.03.2015, 21:25
Mr.X, а не подскажите как перевести этот код на СИ?
0
Эксперт С++
 Аватар для Mr.X
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
01.04.2015, 21:57
Цитата Сообщение от Aseed Посмотреть сообщение
Mr.X, а не подскажите как перевести этот код на СИ?
Ну, вместо std::string нужно использовать сишные нультерминальные строки и функции для работы с ними. Написал бы, но у меня на Си аллергия.
0
0 / 0 / 0
Регистрация: 26.11.2014
Сообщений: 12
01.04.2015, 22:42
Mr.X, спасибо я уже сделал, вот код, может кому понадобится
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
#define _CRT_SECURE_NO_WARNINGS
#include <ctype.h>
#include <stdio.h>
#include <string.h>
#include <locale.h>
#include <stdlib.h>
 
#define N 100
 
int pref_to_postf(char *s, char *res)
{
    char tmp[N];
    
    res[0] = s[0];
    res[1] = 0;
 
    strcpy(tmp, res);
 
    s++;
 
    if (!isalpha(res[0]))
    {
        pref_to_postf(s, res);
        pref_to_postf(s + strlen(res), res + strlen(res));
        strcat(res, tmp);
    }
    
    return 0;
}
 
 
int main()
{
    char s[N], res[N];
    setlocale(LC_ALL, "Russian");
    
    puts("Введите выражение в префиксной форме:");
    fgets(s, N, stdin);
 
    puts("Это же выражение в постфиксной форме:");
    pref_to_postf(s, res);
    printf("%s\n", res);
    
    system("pause");
    return 0;
}
0
0 / 0 / 0
Регистрация: 05.06.2017
Сообщений: 34
25.06.2017, 21:20
помогите сделать из постфиксного в префиксное представление.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
25.06.2017, 21:20
Помогаю со студенческими работами здесь

Перевод из инфиксной записи в постфиксную
Всем привет! Ребята, помогите пожалуйста решить задачу. Нужно написать программу с использованием стека, которая переводит инфиксную запись...

Перевод из инфиксной записи в постфиксную
Программа очень сырая и вообще не работает вовсе. Как исправить ее? def rpn(s): lex=parse(s) s2= r= oper= ...

Преобразовать выражение в префиксной форме в постфиксную (C -> C++)
Помогите пожалуйста перевести программу на язык СИ. #include &lt;cctype&gt; #include &lt;iostream&gt; #include &lt;string&gt; typedef...

Перевод инфиксной формы в постфиксную
Пишу программу для перевода из инфиксной системы в постфиксную, при работе программы выдает ошибку EAccessviolation, и указывает на Stack....

Перевод из префиксной в инфиксную через ArrayList
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace...


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Новые блоги и статьи
Учёным и волонтёрам проекта «Einstein@home» удалось обнаружить четыре гамма-лучевых пульсара в джете Млечного Пути
Programma_Boinc 01.01.2026
Учёным и волонтёрам проекта «Einstein@home» удалось обнаружить четыре гамма-лучевых пульсара в джете Млечного Пути Сочетание глобально распределённой вычислительной мощности и инновационных. . .
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост.
Programma_Boinc 28.12.2025
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / **********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / **********/ gallery/ bKBkQFf Пост отсюда. . .
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США.
Programma_Boinc 26.12.2025
Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка.
Programma_Boinc 23.12.2025
Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Как объединить две одинаковые БД Access с разными данными
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru