Из инфиксной в постфиксную

@sanchoflat · Регистрация: 05.11.2011

Студворк — интернет-сервис помощи студентам

Привет, опять я с этим заданием. Уже глаз болит, не могу понять в чем беда. Проблема при использовании скобок. А если вводить что-то типа A+B-C то он теряет "-"

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
bool stekNil( Stack^ stek, bool *flag,wchar_t q)//проверка на пустоту списка
        {
            *flag = false;
            if ( stek->Count == 0 )
                {
                    *flag = true;
                }
            else *flag = false;
            return *flag;
        }
 
///////////////////////
 
        int prior(wchar_t q, int *prioritet)// приоритет подавайемый на вход
        {
            if ( q == '-' ||q =='+' ) *prioritet= 1;
            else if ( q == '*' || q == '/' ) *prioritet = 2;
            else if ( q == '^' ) *prioritet = 3;
            return *prioritet;
        }
        ///////////////////////////работает
 
        bool proritetStek(int *prior,int *pr, Stack^ stek, bool *flag )
        {           
 
            *flag = false;
            *pr = 0; //приоритет элемента в стеке
            do
                {
                    if ( Convert::ToChar(stek->Peek()) == Convert::ToChar('(')) *pr = 0;
                    if ( Convert::ToChar(stek->Peek()) == Convert::ToChar('-') || Convert::ToChar(stek->Peek()) == '+' )*pr = 1;
                    if (Convert::ToChar(stek->Peek()) == Convert::ToChar('*') || Convert::ToChar(stek->Peek()) == Convert::ToChar('/')) *pr = 2;
                    if (Convert::ToChar(stek->Peek()) == Convert::ToChar('^') ) *pr = 3;
                    if ( *pr<*prior ) // если приоритет в стеке меньше чем на входе
                        *flag = true;
                    else *flag = false;
                    stek->Pop();
                }
                while ( stek->Count != 0);
                return *flag;   
        }
 
/////////////////////////
 
        void verxnielem (int *prior,Stack^ stek,int *pr,Stack^ out )
        {
            *pr=0; // приоритет в стеке
            bool flag1 = false;
            
            while ( stek->Count != 0)
            {
                    flag1 = false;
                    if (Convert::ToChar(stek->Peek()) == Convert::ToChar('-') || Convert::ToChar(stek->Peek()) == Convert::ToChar('+'))*pr = 1;
                    if (Convert::ToChar(stek->Peek()) == Convert::ToChar('*') || Convert::ToChar(stek->Peek()) == Convert::ToChar('/')) *pr = 2;
                    if (Convert::ToChar(stek->Peek()) == '^' ) *pr = 3;
                    
                    if ( *pr>=*prior) //приоритет на вершине стека больше или равен приоритета на входе
                    {
                        flag1 = true;
                        out->Push(stek->Peek());
                        stek->Pop();
                    }
                }
 
        }
 
        ///////////////////////////////////////////////////////
 
        void sakrskobka(Stack^ stek,Stack^ out)
        {
            while ( stek->Peek() != '(' )
                {
                    out->Push(stek->Peek());
                    stek->Pop();
                }
            if ( stek->Peek()== '(' || stek->Peek()== ')')
                stek->Pop();
        }
 
        void peregon(Stack^ out)
        {
            String ^outstr;
            String ^q;
            Stack^ vrem = gcnew Stack;
            while ( out->Count != 0 )
                {
                    vrem->Push(out->Peek());
                    out->Pop();
 
                }
            while ( vrem->Count != 0 )
            {
                    q = Convert::ToString(vrem->Peek());
 
                    outstr = String::Concat(outstr,q);
                    vrem->Pop();
            }
            label5->Text = outstr;      
        }

И сам алгоритм

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
                 int i=0;
                 for (  i=0; i<n; i++)
                    {
                        if ( in[i]>='A' && in[i]<='Z' )
                            {
                                out->Push(Convert::ToString(in[i]));
                            }
                        ///////////////////////////////////////////////
                        else if ( in[i]=='-' || in[i]=='+' || in[i]=='/' || in[i]=='*' || in[i]=='^' )
                            {
                                q=in[i];
                                prior( q, &prioritet); //проверяем приоритет на входе
                                stekNil(stek,&flag,q); // проверяем пустоту стека
                                if ( flag == true ) // если пустой - помещаем элемент в стек
                                    {   
                                        stek->Push(in[i]);
                                    }
 
 
                                else // если стек полон, проверяем приоритет элементов в стеке. Если приоритет в стеке меньше чем на входе - помещаем в стек
 
                                    if ( proritetStek(&prioritet,&pr,gcnew Stack(stek),&flag )==true)
                                    {
                                         stek->Push(in[i]);
                                    }
                                 
                                    else  // иначе если приоритет элемента в стеке больше или равен приоритета на входе - вытаскиваем эл. из стека в выходной стек
 
                                    verxnielem (&prioritet,gcnew Stack(stek),&pr,out);
 
                            }
 
 
                        if ( in[i] == '(') // если открывающаяся скобка - помещаем в стек
                            {
                                stek->Push(in[i]);
                            }
                        
                        if ( in[i] == ')') // если закрывающаяся скобка - вытаскиваем элементы из стека в выходной стек, пока не встретим откр. скобку.
                            {
                                sakrskobka(gcnew Stack(stek),out);
                            }
                 }
 
                 if ( i == n ) // если элемент в строке последний, то вытаскиваем элементы из стека в выходной
                    {
                        MessageBox::Show(Convert::ToString(stek->Count));
                        flag = true;
                        while ( flag)
                            {
                                out->Push(stek->Peek());
                                stek->Pop();
                                if ( stek->Count == 0)
                                    flag = true;
                                else flag = false;
                            }
                    }
 
                 MessageBox::Show(Convert::ToString(stek->Peek()));
                 peregon(out);// перегон из выходного стека в строку и вывод в label

@rinat_w · 05.11.2012, 11:50

sanchoflat, напиши полное условие

@sanchoflat · 05.11.2012, 14:11 **[ТС]**

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

Добавлено через 5 минут
Алгоритм брал такой:

1. Если этот символ - число (или переменная), то просто помещаем его в выходную строку.
2. Если символ - знак операции (+, -, *, / ), то проверяем приоритет данной операции. Операции умножения и деления имеют наивысший приоритет (допустим он равен 3). Операции сложения и вычитания имеют меньший приоритет (равен 2). Наименьший приоритет (равен 1) имеет открывающая скобка.
Получив один из этих символов, мы должны проверить стек:
а) Если стек все еще пуст, или находящиеся в нем символы (а находится в нем могут только знаки операций и открывающая скобка) имеют меньший приоритет, чем приоритет текущего символа, то помещаем текущий символ в стек.
б) Если символ, находящийся на вершине стека имеет приоритет, больший или равный приоритету текущего символа, то извлекаем символы из стека в выходную строку до тех пор, пока выполняется это условие; затем переходим к пункту а).
3. Если текущий символ - открывающая скобка, то помещаем ее в стек.
4. Если текущий символ - закрывающая скобка, то извлекаем символы из стека в выходную строку до тех пор, пока не встретим в стеке открывающую скобку (т.е. символ с приоритетом, равным 1), которую следует просто уничтожить. Закрывающая скобка также уничтожается.

Если вся входная строка разобрана, а в стеке еще остаются знаки операций, извлекаем их из стека в выходную строку.

Добавлено через 2 часа 13 минут
Немного подделал алгоритм. Добавил цикл, однако непонятно почему он зацикливается?

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
    else if ( in[i]=='-' || in[i]=='+' || in[i]=='/' || in[i]=='*' || in[i]=='^' )
                            {
                            do
                            {
                                test = false;
                                q=in[i];
                                prior( q, &prioritet); //проверяем приоритет на входе                          
                                    stekNil(stek,&nil,q); // проверяем пустоту стека
                                    if ( nil == true ) // если пустой - помещаем элемент в стек
                                        {   
                                            stek->Push(in[i]);
                                            MessageBox::Show("JH");
                                        }
 
                                    else if ( proritetStek(&prioritet,&pr,gcnew Stack(stek),&priors )==true)// если стек полон, проверяем приоритет элементов в стеке. Если приоритет в стеке меньше чем на входе - помещаем в стек           
                                                {
                                                     stek->Push(in[i]);
                                                }
                                    else 
                                    {
                                    verxnielem (&prioritet,gcnew Stack(stek),&pr,out, &verx);
                                    if (verx == true)
                                        {
                                            test = true ;
                                            MessageBox::Show("D");
                                        }
                                    }
                                }
                                while (test == true);
                            }
 
 
                        if ( in[i] == '(') // если открывающаяся скобка - помещаем в стек
                            {
                                stek->Push(in[i]);
                            }
                        
                        if ( in[i] == ')') // если закрывающаяся скобка - вытаскиваем элементы из стека в выходной стек, пока не встретим откр. скобку.
                            {
                                sakrskobka(gcnew Stack(stek),out);
                            }
                 }

Новые блоги и статьи Все статьи Все блоги /
Unity 4D GameUnited 13.06.2025 Четырехмерное пространство. . . Звучит как что-то из научной фантастики, правда? Однако для меня, как разработчика со стажем в игровой индустрии, четвертое измерение давно перестало быть абстракцией из. . .	SSE (Server-Sent Events) в ASP.NET Core и .NET 10 UnmanagedCoder 13.06.2025 Кажется, Microsoft снова подкинула нам интересную фичу в новой версии фреймворка. Работая с превью . NET 10, я наткнулся на нативную поддержку Server-Sent Events (SSE) в ASP. NET Core Minimal APIs. Эта. . .	С днём независимости России! Hrethgir 13.06.2025 Решил побеседовать, с утра праздничного дня, с LM о завоеваниях. То что она написала о народе, представителем которого я являюсь сам сначала возмутило меня, но дальше только смешило. Это чисто. . .	Лето вокруг. kumehtar 13.06.2025 Лето вокруг. Наполненное бурями и ураганами событий. На фоне магии Жизни, священной и вечной, неумелой рукой человека рисуется панорама душевного непокоя. Странные серые краски проникают и. . .	Популярные LM модели ориентированы на увеличение затрат ресурсов пользователями сгенерированного кода (грязь -заслуги чистоплюев). Hrethgir 12.06.2025 Вообще обратил внимание, что они генерируют код (впрочем так-же ориентированы разработчики чипов даже), чтобы пользователь их использующий уходил в тот или иной убыток. Это достаточно опытные модели,. . .
Топ10 библиотек C для квантовых вычислений bytestream 12.06.2025 Квантовые вычисления - это та область, где теория встречается с практикой на границе наших знаний о физике. Пока большая часть шума вокруг квантовых компьютеров крутится вокруг языков высокого уровня. . .	Dispose и Finalize в C# stackOverflow 12.06.2025 Работая с C# больше десяти лет, я снова и снова наблюдаю одну и ту же историю: разработчики наивно полагаются на сборщик мусора, как на волшебную палочку, которая решит все проблемы с памятью. Да,. . .	Повышаем производительность игры на Unity 6 с GPU Resident Drawer GameUnited 11.06.2025 Недавно копался в новых фичах Unity 6 и наткнулся на GPU Resident Drawer - штуку, которая заставила меня присвистнуть от удивления. По сути, это внутренний механизм рендеринга, который автоматически. . .	Множества в Python py-thonny 11.06.2025 В Python существует множество структур данных, но иногда я сталкиваюсь с задачами, где ни списки, ни словари не дают оптимального решения. Часто это происходит, когда мне нужно быстро проверять. . .	Работа с ccache/sccache в рамках C++ Loafer 11.06.2025 Утилиты ccache и sccache занимаются тем, что кешируют промежуточные результаты компиляции, таким образом ускоряя последующие компиляции проекта. Это означает, что если проект будет компилироваться. . .

@rinat_w 92 / 88 / 17 Регистрация: 13.11.2011 Сообщений: 193
	05.11.2012, 11:50
	sanchoflat, напиши полное условие 0

Опции темы