Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
sanchoflat
4 / 6 / 1
Регистрация: 05.11.2011
Сообщений: 97
05.11.2012, 11:48     Из инфиксной в постфиксную #1
Привет, опять я с этим заданием. Уже глаз болит, не могу понять в чем беда. Проблема при использовании скобок. А если вводить что-то типа 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
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.11.2012, 11:48     Из инфиксной в постфиксную
Посмотрите здесь:

Выражение в инфиксной форме. СРОЧНО!!! C++
C++ Преобразовать выражение в постфиксную форму
Перевести выражение из инфиксной формы в постфиксную C++
Из инфиксной нотации в постфиксную C++
C++ Перевести префиксную запись выражения в постфиксную
C++ Перевод из инфиксной в постфиксную запись
Преобразования инфиксной формы в постфиксную Turbo Pascal
Преобразовать выражение в префиксной форме в постфиксную (C -> C++) C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
rinat_w
89 / 85 / 4
Регистрация: 13.11.2011
Сообщений: 183
05.11.2012, 11:50     Из инфиксной в постфиксную #2
sanchoflat, напиши полное условие
sanchoflat
4 / 6 / 1
Регистрация: 05.11.2011
Сообщений: 97
05.11.2012, 14:11  [ТС]     Из инфиксной в постфиксную #3
Используя стек, определить функцию, которая переводит выражение, записанное в обычной (инфиксной) форме в постфиксную форму. Предусмотреть ввод выражения с клавиатуры и из текстового файла.


Добавлено через 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);
                            }
                 }
Yandex
Объявления
05.11.2012, 14:11     Из инфиксной в постфиксную
Ответ Создать тему
Опции темы

Текущее время: 02:36. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru