Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.77/13: Рейтинг темы: голосов - 13, средняя оценка - 4.77
2 / 2 / 1
Регистрация: 31.08.2012
Сообщений: 22

Провести лексический анализ строки и сказать является ли она верным арифметическим выражением

31.08.2012, 22:46. Показов 2855. Ответов 7
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Прошу сильно не пинать, т.к. только начал изучать дискретку.

Есть некоторый алфавит состоящий из чисел типа double, и следующих операций
/ * + - ( )
Плюс и минус могут быть как унарными, так и бинарными.

На входе строка (System.String) над предложенным алфавитом, нужно
1. Провести лексический анализ строки и сказать является ли она верным арифметическим выражением
2. Вычислить данное арифметическое выражение.

Может у кого-то есть реализация подобного конечного автомата (код или блок-схема), если поделитесь буду очень признателен.
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
31.08.2012, 22:46
Ответы с готовыми решениями:

Определить, является ли заданный текст арифметическим выражением
Уважаемые программист(ы)! Очень прошу помочь решить еще одну задачку, условие которой звучит так: Определить, является ли заданный текст...

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

Определить, является ли заданная последовательность символов арифметическим выражением
Определить, является ли заданная последовательность символов арифметическим выражением, состоящий из целых чисел и четырех основных...

7
 Аватар для xnimor
72 / 72 / 6
Регистрация: 16.06.2012
Сообщений: 220
31.08.2012, 23:50
эммм... все просто по идее... создайте таблицу - строки - входной символ, столбцы - реакция.
Насколько я понимаю Вы должны обработать значение на "корректность"?

Тогда делать так - сперва выделить токены - отдельно число, знак, скобка.

Для выделения числа (и проверки на корректность) аналогично выражению - нужен автомат.
Автомат для проверки числа (пример из моего кода)
C++ (Qt)
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
bool FSM_Calc::isFloat()
{//Осуществляет проверку на число
    enum FloatTypes 
    {//метки для автомата
        start = 0,
        neg = 1,
        integer = 2,
        point = 3,
        extint = 4,
        err = 100,
        ok = 101
    };
    FloatTypes FSM[5][4] = 
    {//таблица с описанием автомата
        {neg,integer,point,err},
        {err,integer,point,err},
        {err,integer,point,ok},
        {err,extint,err,err},
        {err,extint,err,ok}
    },Result = start;
    char *& A = token;
    int i = -1;
    do //обработка символов
    {
        i++;
        if (!A[i]) Result = FSM[Result][3];
        if (Result>=100) return Result - err;//если ошибка, либо верное число
        if (A[i] == '-') Result = FSM[Result][0];//число отрицательное
        else
            if(A[i] >='0' && A[i] <='9') Result = FSM[Result][1];
            else 
                if(A[i] == '.') Result = FSM[Result][2];//дробное
    } while (A[i]);
}
Здесь привел несколько комментов - думаю, помогут.
Если коротко - то таблица (обычно рисуется на бумаге)

Пример таблицы, описывающей автомат:
HTML5
1
2
3
4
5
6
                         /цифра             / точка        / другой символ / конец строки
start                  / Целая часть   /     ошибка     /   ошибка     /       ок
 
Целая часть        /  целая          /   дробная     /    ошибка     /      ок
 
Дробная часть     /  дробная        /    ошибка   /      ошибка     /      ок
Добавлено через 17 минут
В коде добавлена по строке - "отрицательность"
В столбце - знак минус
1
 Аватар для xnimor
72 / 72 / 6
Регистрация: 16.06.2012
Сообщений: 220
01.09.2012, 01:18
Кинул проект на C++, ибо переписать на шарп, думаю сложности не представится...
1
Master of Orion
Эксперт .NET
 Аватар для Psilon
6102 / 4958 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
01.09.2012, 02:08
Моя программа ниже. Работают: все арифметические операции, открывающая и закрывающая скобки. Весь код прокомментирован. Если нужно, ниже целиковый проект. Есть все, кроме унарного плюса и минуса.
Programm.cs
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
using System;
 
namespace MyMath
{
    class Program
    {
        static void Main()
        {
            while (true)
            {
                Console.WriteLine("Введите выражение для вычисления. Для выхода напишите exit");
                string s = Console.ReadLine();
                if (s == "exit")
                    return;
                var result = CalculateExpression.Calculate(s);
                if (result == null)
                    Console.WriteLine("Неправильный формат ввода");
                else
                    Console.WriteLine(result);
            }
        }
    }
}
CalculateExpression.cs
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
112
113
114
115
116
117
118
119
120
121
122
using System;
using System.Collections.Generic;
using System.Text;
 
namespace Math
{
    public static class CalculateExpression
    {
        private static readonly Dictionary<char, byte> _opdict = new Dictionary<char, byte> { { '+', 1 }, { '-', 2 }, { '/', 3 }, { '*', 4 }, { '(', 0 } };
 
        private static readonly HashSet<char> _operators = new HashSet<char> {'+', '-', '/', '*'};
 
        private static double CalculateSimple(double a, double b, char op) //Выполняем нужное вычисление в зависимости от операции
        {
            double result = 0;
            switch (op)
            {
                case '+':
                    result = a + b;
                    break;
                case '-':
                    result = a - b;
                    break;
                case '*':
                    result = a*b;
                    break;
                case '/':
                    result = a/b;
                    break;
            }
            return result;
        }
 
        private static double StackCalc(double a, double b, char op) //Так как из стека достаем в обратном порядке, требуется инвертировать левый и правый операнды
        {
            return CalculateSimple(b, a, op);
        }
 
        private static bool BadBreckets(string s) //Проверяем баланс скобок в строке
        {
            int i = 0;
            foreach (var c in s)
            {
                if (c == '(')
                    i++;
                else if (c == ')')
                    i--;
            }
            return i != 0;
        }
 
        private static string Reverse(string s) //Обращаем строку в обратный порядок
        {
            int length = s.Length;
            var sb = new StringBuilder(s.Length, s.Length);
            for (int i = length - 1; i >= 0; i--)
                sb.Append(s[i]);
            return sb.ToString();
        }
        
        public static string ToRPN(string input) //Для более удобного анализа переводим в ОПН
        {
            string result = "";
            var stack = new Stack<char>();
            foreach (char c in input)
            {
                if (c == '(') 
                    stack.Push(c);
                else if (c == ')')//Если встречаем закрывающую скобку, то вытряхиваем в строку все, до появления открывабщей скобки
                {
                    while (stack.Count > 0)
                    {
                        char a = stack.Pop();
                        if (a == '(') break;
                        result += " " + a;
                    }
                }
                else if (_operators.Contains(c))//Иначе если это оператор, вытряхиваем все операторы с большим приоритетом в строку, после этого засовываемся сами в стек
                {
                    result += " ";
                    while (stack.Count > 0 && _opdict[c] < _opdict[stack.Peek()])
                    {
                        result += stack.Pop() + " ";
                    }
                    stack.Push(c);
                }
                else result += c;  //Если это не скобки и не операторы, то это цифра, добавляем к выходной строке
            }
            while (stack.Count > 0) //Вытряхиваем в строку оставшиеся символы
                result += " " + stack.Pop();
            return result;
        }
 
        public static string ToPN(string input)
        {
            return Reverse(ToRPN(input));
        }
 
        public static double? Calculate(string input) //Вычисляем выражение. Если формат ввода неправильный, возвращаем null
        {
            if (BadBreckets(input) || String.IsNullOrEmpty(input))
                return null;
            var strings = ToRPN(input).Split(new[] {' '}, StringSplitOptions.RemoveEmptyEntries);
            var stack = new Stack<double>(input.Length/2);
            foreach (var s in strings)
            {
                if (_opdict.ContainsKey(s[0])) //Если оператор, то выполняем его над последними двумя элементами стека.
                {
                    if (stack.Count < 2) return null;
                    stack.Push(StackCalc(stack.Pop(), stack.Pop(), s[0]));
                }
                else //Иначе это должно быть число, если вдруг что-то другое, то возвращаем null
                {
                    double a;
                    if (!double.TryParse(s, out a)) return null;
                    stack.Push(a);
                }
            }
            return System.Math.Round(stack.Peek(), 15); //В стеке остается единственный элемент, значение выражения, который возвращаем
        }
    }
}
Вложения
Тип файла: rar MyMath.rar (45.2 Кб, 26 просмотров)
2
Master of Orion
Эксперт .NET
 Аватар для Psilon
6102 / 4958 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
01.09.2012, 02:20
А в этом варианте унарные операции тоже работают (смотрите сами, что изменилось )
Хотя и не всегда. А то том ,как сделать всегда, можете сами догадаться. Ну или подождать, пока я придумаю
Вложения
Тип файла: rar MyMath(new).rar (45.4 Кб, 28 просмотров)
1
Master of Orion
Эксперт .NET
 Аватар для Psilon
6102 / 4958 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
01.09.2012, 02:54
В общем, у меня есть работающая программа для правильной работы с унарными операторами, если интересно, потом выложу (вернее, если вам неинтересно самому сделать). А этот вариант сойдет для любых бинарных

Не по теме:

Почему посты не клеются?:(

1
2 / 2 / 1
Регистрация: 31.08.2012
Сообщений: 22
01.09.2012, 11:33  [ТС]
xnimor, Psilon огромное спасибо вам за помощь, думаю теперь с реализацией у меня проблем не возникнет.

Цитата Сообщение от Psilon Посмотреть сообщение
В общем, у меня есть работающая программа для правильной работы с унарными операторами, если интересно, потом выложу (вернее, если вам неинтересно самому сделать). А этот вариант сойдет для любых бинарных
лучше попробую сам
0
01.09.2012, 19:58

Не по теме:

Цитата Сообщение от Psilon Посмотреть сообщение
Почему посты не клеются
Потому что в одном из них было вложение

1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
01.09.2012, 19:58
Помогаю со студенческими работами здесь

Если введённая строка является вычислимым арифметическим выражением, то вычислить его
Друзья, помогите, завтра сдать нужно, а я все никак не додумаюсь. Нужно написать программку на простом &quot;СИ&quot; ну как консольное...

Дана строка символов до точки. Определить, является ли она правильным скобочным выражением. Рассматривать только круглые скобки.
Дана строка символов до точки. Определить, является ли она правильным скобочным выражением. Рассматривать только круглые скобки.


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

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Новые блоги и статьи
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++
8Observer8 10.03.2026
Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:
Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE
8Observer8 10.03.2026
Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки
Neotwalker 08.03.2026
Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages
DevAlt 07.03.2026
Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F#
DevAlt 06.03.2026
В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .
Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование
8Observer8 05.03.2026
Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D
8Observer8 03.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий
8Observer8 02.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru