Форум программистов, компьютерный форум, киберфорум
C# .NET
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.96/25: Рейтинг темы: голосов - 25, средняя оценка - 4.96
 Аватар для Kill100
434 / 299 / 82
Регистрация: 11.12.2010
Сообщений: 1,209
.NET 4.x

Преобразовать строку в обратную польскую запись.

01.10.2011, 17:22. Показов 4794. Ответов 13
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Собственно как это реализовать.
Например входная строка "AvB" (где A и B заглавные симвволы)
должен получить "B A v"
А этот код пишет "A B"
Описание стека;
Стек перставлен в виде универсального класса.
и имеет следующие методы.

Add(X) добавляет элемент в начало;
Del() удаляет ээлемент;
Del_And_ReturnData() Возвращает значение 1 (с верху) элемента и удаляет его;
Del_Next_And_ReturnData() Возвращает значение 2 (с верху) элемента и удаляет его; PS знаю что получился не совсем стек... Если такого нету то Ошибка
ToString() Возвращает все элементы стека в виде строки.
Поля
Data первый элемент стека
DataNext // второй элемент стека если есть
Сам класс стека
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
    class item<TypeStack>
    {
        #region класс элемента списка
        private class ItemS
        {
            private TypeStack _Data;
            private ItemS _Next;
            public TypeStack Data
            {
                get
                {
                    return _Data;
                }
                set
                {
                    _Data = value;
                }
            }
            public ItemS Next
            {
                get
                {
                    return _Next;
                }
                set
                {
                    _Next = value;
                }
            }
        }
        #endregion
        
        ItemS it = new ItemS();
 
        public void Add(TypeStack chislo)
        {
            ItemS a = new ItemS();
            a.Data = chislo;
            a.Next = it;
            it = a;
        }
 
        public void Del()
        {
            it = it.Next;
        }
 
        public TypeStack Del_And_ReturnData()
        {
            TypeStack s = it.Data;
            it = it.Next;
            return s;
        }
 
        public TypeStack Del_Next_And_ReturnData()
        {
            TypeStack s = it.Next.Data;
            if (it.Next.Next != null)
            {
                ItemS a = new ItemS();
                a.Data = it.Data;
                a.Next = it.Next.Next;
                it = a;
            }
            else
            {
                throw new Exception("Null");
            }
            return s;
        }
 
        public override string ToString()
        {
            string s = "";
            ItemS ss = it;
            while (ss.Next != null)
            {
                s += ss.Data + " ";
                ss = ss.Next;
            }
            return s;
        }
 
        public TypeStack Data
        {
            get { return it.Data; }
        }
 
        public TypeStack DataNext
        {
            get { return it.Next.Data; }
        }
    }

Код программы
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
  private string polsk(string Text)
        {
            string s = "";
            item<char> stack = new item<char>();
            char [] mass = Text.ToCharArray();
            for (int i = 0; i < mass.Length; i++)
            {
                if (mass[i] >= 'A' && mass[i] <= 'Z')
                {
                    s += " " + mass[i];
                }
                if(mass[i]=='!'||mass[i]=='v'||mass[i]=='^'||mass[i]=='→'||mass[i]=='↔'||mass[i]=='(')
                {
                    stack.Add(mass[i]);
                }
                if (mass[i] == ')')
                {
                    if (stack.Data != ')')
                        s += " " + stack.Del_And_ReturnData();
                    else
                        stack.Del();
                }
            }
            return s;
        }
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
01.10.2011, 17:22
Ответы с готовыми решениями:

Калькулятор: сделать обратную польскую запись
есть инженерный калькулятор, нужно сделать обратную польскую запись или другими словами сделать приоритетность действий...помогите...

Преобразование математической формулы в обратную польскую запись
Нужен исходник по переводу математической формулы типа &quot;a+b*c(e/d)&quot; в обратную польскую используя стек.

Ошибка в алгоритме преобразования выражения в обратную польскую запись
Метод OPLConvert принимает выражение в виде строки, например &quot;2+2*2&quot;. Пока что без учета приоритета операторов хочу чтобы мне мой метод...

13
Эксперт .NET
 Аватар для kolorotur
17823 / 12973 / 3382
Регистрация: 17.09.2011
Сообщений: 21,261
01.10.2011, 17:31
Реализуйте алгоритм Shunting Yard за авторством Дейкстры и будет вам счастье.

Кстати, зачем вам самопальный стэк? Готовый класс уже есть в System.Collection.Generics
0
 Аватар для Kill100
434 / 299 / 82
Регистрация: 11.12.2010
Сообщений: 1,209
01.10.2011, 17:40  [ТС]
Цитата Сообщение от kolorotur Посмотреть сообщение
Реализуйте алгоритм Shunting Yard за авторством Дайкстры и будет вам счастье.

Кстати, зачем вам самопальный стэк? Готовый класс уже есть в System.Collection.Generics
Я знаю что есть встроенный стек.

Тут такое дело просто в лабораторке так написанно
Написать стек типа "char" и с его помощью преобразовать... Но на тип мне ... По этому сделал универсальным.
0
Эксперт .NET
 Аватар для kolorotur
17823 / 12973 / 3382
Регистрация: 17.09.2011
Сообщений: 21,261
01.10.2011, 18:04
Дело было вечером, делать было нечего...
Я как-то баловался в шарпе и вот накатал некое подобие реализации алгоритма Дайкстры:

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
static void Main(string[] arg)
        {
            var log = LogManager.GetCurrentClassLogger();
            var output = new Queue<string>();
            var operators = new Stack<string>();
            string input = Console.In.ReadToEnd();
            for (int i = 0; i < input.Length; i++){
                char token = input[i];
 
                if (char.IsNumber(token)) {
                    int j = i + 1;
                    while (j < input.Length && (char.IsNumber(input[j]) || input[j] == '.')) j++;
                    var value = input.Substring(i, j-i);
                    i = j - 1;
                    output.Enqueue(value);
                    log.Trace("Enqueue {0}", value);
                } else if (char.IsLetter(token)) {
                    int j = 0;
                    while (j < input.Length && char.IsLetter(input[j])) j++;
                    var function = input.Substring(i, j-i);
                    operators.Push(function.ToString());
                    log.Trace("Push {0}", function);
                } else if (token == ',') {
                    while (operators.Peek() != "(") {
                        log.Trace("Pop {0} to output", operators.Peek());
                        output.Enqueue(operators.Pop());
                    }
                    if (operators.Count == 0)
                        throw new FormatException("The separator was misplaced or parentheses were mismatched.");
                } else if (IsOperator(token)) {
                    if (token == '-') {
                        log.Info("{0}    {1}", string.Join(" ", output.ToArray()), string.Join(" ", operators.ToArray()));
                        Console.ReadKey();
                    }
                    while (operators.Count > 0 && IsOperator(operators.Peek()) && ( ( IsLeftAssociative(token) && Precedense(token) <= Precedense(operators.Peek()) ) || IsRightAssociative(token) && Precedense(token) < Precedense(operators.Peek()) )) {
                        log.Trace("Pop {0} to output", operators.Peek());
                        output.Enqueue(operators.Pop());
                    }
                    operators.Push(token.ToString());
                    log.Trace("Push {0}", token);
                } else if (token == '(') {
                    operators.Push(token.ToString());
                    log.Trace("Push {0}", token);
                } else if (token == ')') {
                    while (operators.Count > 0 && operators.Peek() != "(") {
                        log.Trace("Pop {0} to output", operators.Peek());
                        output.Enqueue(operators.Pop());
                        if (operators.Count == 0)
                            throw new FormatException("Mismatched parentheses");
                    }
                    log.Trace("Pop {0}", operators.Pop()); // Pop the left paranthesis
 
                    if (operators.Count > 0) {
                        var top = operators.Peek();
                        if (!IsOperator(top) && top != ")" && top != "(") {
                            log.Trace("Pop {0} to output", top);
                            output.Enqueue(operators.Pop());
                        }
                    }
                } else {
                    continue;
                }
 
                log.Debug("{0} | {1}", string.Join(" ", output.ToArray()), string.Join(" ", operators.ToArray()));
            }
 
            while (operators.Count > 0)
                if (operators.Peek() == "(" || operators.Peek() == ")")
                    throw new FormatException("Mismatched parentheses");
                else {
                    log.Trace("Pop {0} to output", operators.Peek());
                    output.Enqueue(operators.Pop());
                    log.Debug("{0} | {1}", string.Join(" ", output.ToArray()), string.Join(" ", operators.ToArray()));
                }
                
                string reversePolish = string.Join(" ", output.ToArray());
 
            Console.ReadKey();
        }
        static bool IsOperator(string token)
        {
            return token.Length == 1 && IsOperator(token[0]);
        }
        static bool IsOperator(char token)
        {
            return token == '-' || token == '+' || token == '/' || token == '*' || token == '^';
        }
        static bool IsLeftAssociative(char token)
        {
            return IsOperator(token) && token != '^';
        }
        static bool IsRightAssociative(char token)
        {
            return token == '^';
        }
        static int Precedense(string token)
        {
            if (token.Length != 1)
                throw new FormatException(string.Format("String '{0}' is not a valid operator", token));
 
            return Precedense(token[0]);
        }
        static int Precedense(char token)
        {
            if (token == '+' || token == '-') return 2;
            if (token == '*' || token == '/') return 3;
            if (token == '^') return 4;
            throw new FormatException(token + " is not a valid operator");
        }
Код не идеальный, в частности он не учитывает случай со знаком "-" в качестве отображения негативного числа, а не оператора. Но в целом дает примерное представление о перегоне математического выражения в обратную польскую нотацию.

P.S. Переменная log - это, собственно, логгер - для себя. Все, что с ней связано, можно смело удалять из кода
0
 Аватар для Kill100
434 / 299 / 82
Регистрация: 11.12.2010
Сообщений: 1,209
01.10.2011, 19:33  [ТС]
а как проверить ответ на верность?
Допустим я ввел
AvB^(C→(B^!A))
а получил
A B C B A ! ^ → ^ v

поправил но все равно не верно...
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 string s = "";
            item<char> stack = new item<char>();
            char [] mass = Text.ToCharArray();
            for (int i = 0; i < mass.Length; i++)
            {
                if (mass[i] >= 'A' && mass[i] <= 'Z')
                {
                    s += " " + mass[i];
                }
                if (mass[i] == '!' || mass[i] == 'v' || mass[i] == '^' || mass[i] == '→' || mass[i] == '↔' || mass[i] == '(')
                {
                    stack.Add(mass[i]);
                }
                if (mass[i] == ')')
                {
                    while (stack.Data != '(')
                        s += " " + stack.Del_And_ReturnData();
                    stack.Del();
                }
            }
            s += " " + stack.ToString();
            return s;
0
Эксперт .NET
 Аватар для kolorotur
17823 / 12973 / 3382
Регистрация: 17.09.2011
Сообщений: 21,261
01.10.2011, 20:01
Цитата Сообщение от Kill100 Посмотреть сообщение
а как проверить ответ на верность?
Можно на бумажке перегнать и проверить результаты.
Как вариант, реализовать алгоритм вычисления выражений и проверить правильность результата.
0
 Аватар для Kill100
434 / 299 / 82
Регистрация: 11.12.2010
Сообщений: 1,209
02.10.2011, 17:39  [ТС]
повозился повозился и что то не получается...
0
Эксперт .NET
 Аватар для kolorotur
17823 / 12973 / 3382
Регистрация: 17.09.2011
Сообщений: 21,261
02.10.2011, 17:43
Что именно не получается?
0
 Аватар для Kill100
434 / 299 / 82
Регистрация: 11.12.2010
Сообщений: 1,209
02.10.2011, 22:33  [ТС]
Цитата Сообщение от kolorotur Посмотреть сообщение
Что именно не получается?
Попробовал реализовать алгоритм из вики.
Алгоритм

1)Пока есть ещё символы для чтения:
2)Читаем очередной символ.
3)Если символ является числом, добавить его к выходной строке.
4)Если символ является символом функции, помещаем его в стек.
5)Если символ является открывающей скобкой, помещаем его в стек.
6)Если символ является закрывающей скобкой:
7)До тех пор, пока верхним элементом стека не станет открывающая скобка, выталкиваем элементы из стека в выходную строку. При этом открывающая скобка удаляется из стека, но в выходную строку не добавляется. Если после этого шага на вершине стека оказывается символ функции, выталкиваем его в выходную строку. Если стек закончился раньше, чем мы встретили открывающую скобку, это означает, что в выражении либо неверно поставлен разделитель, либо не согласованы скобки.
8)
Если символ является оператором о1, тогда:
1) пока…
… (если оператор o1 ассоциированный, либо лево-ассоциированный) приоритет o1 меньше либо равен приоритету оператора, находящегося на вершине стека…
… (если оператор o1 право-ассоциированый) приоритет o1 меньше приоритета оператора, находящегося на вершине стека…
… выталкиваем верхние элементы стека в выходную строку;
2) помещаем оператор o1 в стек.
Когда входная строка закончилась, вытолкнуть все символы из стека в выходную строку. В стеке должны были остаться только символы операторов; если это не так, значит в выражении не согласованы скобки.

С 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
        private string polsk(string Text)
        {
            string s = "";
            item<char> stack = new item<char>();
            char [] mass = Text.ToCharArray();
            for (int i = 0; i < mass.Length; i++)
            {
                if (mass[i] >= 'A' && mass[i] <= 'Z')
                {
                    s += " " + mass[i];
                }
                if (mass[i] == '!' || mass[i] == 'v' || mass[i] == '^' || mass[i] == '→' || mass[i] == '↔' || mass[i] == '(')
                {
                    stack.Add(mass[i]);
                }
                if (mass[i] == ')')
                {
                    while (stack.Data != '(')
                        s += " " + stack.Del_And_ReturnData();
                    stack.Del();
                }
            }
            s += " " + stack.ToString();
            return s;
        }
0
Эксперт .NET
 Аватар для kolorotur
17823 / 12973 / 3382
Регистрация: 17.09.2011
Сообщений: 21,261
02.10.2011, 23:41
Да все очень просто, давайте начнем с основ.
Вы, я так понимаю, реализуете алгоритм для логических выражений.
Вот у нас есть логические операторы: !, ∨, ∧, ⊻, ←, →
Начните с того, что для каждого из них определите ассоциированность и приоритет - они нам потребуются во время парса строки.
Как определитесь, восьмой шаг станет довольно простым условием: проверяем данный оператор на ассоциированность и приоритет с оператором, находящимся сверху стэка. Если наш оператор ниже по приоритету или лево-ассоциированный, то выталкиваем операторы из стэка и вставляем в конец готовой строки.
1
 Аватар для Kill100
434 / 299 / 82
Регистрация: 11.12.2010
Сообщений: 1,209
03.10.2011, 14:10  [ТС]
ассациативноссть и приоретет...
Это как???
Где ни будь алгоритм есть хотя бы на псевдо коде...
0
Эксперт .NET
 Аватар для kolorotur
17823 / 12973 / 3382
Регистрация: 17.09.2011
Сообщений: 21,261
03.10.2011, 15:26
Цитата Сообщение от Kill100 Посмотреть сообщение
ассациативноссть и приоретет...
Ассоциативность - порядок выполнения при наличии одного и того же оператора и отстутствие скобок.
Например:
A -> B -> C. В каком порядке выполнять? Сначала B -> C, а потом A -> [результат] или сначала A -> B, а потом [результат] -> C? Если первый вариант, то оператор -> - правоассоциативный, если второй вариант, то левоассоциативный. Если без разницы (A V B V C, например), то ассоциативность отсутствует. Для простоты можно приравнять к левоассоциативным.
Или вот оператор "!" - он явно правоассоциативный, т.к. !!!!A - сначала высчитываем !А, потом !!А и т.д., то есть идем справа налево.
Это надо определить для каждого оператора.

Приоритет - ну это как в арифметике: какой оператор используется в первую очередь при отсутствие скобок. Например, выражение A V B ^ C. Логическое "И" имеет приоритет выше, чем "ИЛИ", потому сначала высчитываем B ^ C, а потом результат V A. Как в математике: x + y * z - сначала умножение, потом сложение. Для каждого оператора надо определить свой приоритет. Чем число выше, например, тем больше приоритет оператора. Это будет использоваться в условиях восьмого шага алгоритма.

Цитата Сообщение от Kill100 Посмотреть сообщение
Где ни будь алгоритм есть хотя бы на псевдо коде...
Алгоритм чего? Если вы про ассоциативность и приоритеты, то это величины постоянные, определенные единожды. Почитать про них можно, наверное, в любом учебнике логики.

Можно конечно обойтись и без всех этих прелестей, но тогда пользователь будет обязан каждое вычисление обводить скобками, чтобы было понятно что сперва, а что - потом.
1
168 / 140 / 23
Регистрация: 02.01.2011
Сообщений: 913
03.10.2011, 16:26
Посмотрите в этой ветке выложенныи мною код, может, поможет
Решить пример записанный обратной польской
0
 Аватар для Kill100
434 / 299 / 82
Регистрация: 11.12.2010
Сообщений: 1,209
05.10.2011, 23:45  [ТС]
для строки !Av(B>(C<>!D)^A)
такая запись верна? A ! B C D ! <> > A ^ v
А то я не уверен ...
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
05.10.2011, 23:45
Помогаю со студенческими работами здесь

Преобразование обычных выражений в обратную польскую запись с помощью стэка
Помогите пожалуйста написать программу для преобразование обычных выражений в обратную польскую запись с помощью стэка, например есть...

Как использовать обратную польскую запись для решения дробно-рациональных уравнений
Как использовать обратную польскую запись для решения дробно-рациональных уравнений? строка ввода в textBox

Преобразование выражения в польскую запись
Помогите, пожалуйста, преобразовать выражение (d + g + h) / c - t * j в польскую запись.

Преобразовать строку из TextBox в обратную польскую запись
Нужно преобразовать строку из TextBox в обратную польскую запись. Проблема в том, что кроме '+','-,'*','\' &quot; встречаются и логические...

Строку в обратную польскую запись
Подскажите, как представить выражение из строки в обратную польскую запись и потом посчитать? Наверное есть уже готовые алгоритмы...


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

Или воспользуйтесь поиском по форуму:
14
Ответ Создать тему
Новые блоги и статьи
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/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru