Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.57/89: Рейтинг темы: голосов - 89, средняя оценка - 4.57
 Аватар для Dennis Ritchie
555 / 148 / 58
Регистрация: 27.07.2014
Сообщений: 2,446

Распарсить выражение, состоящее из чисел, скобок и знаков сложения и вычитания, и вывести результат

05.11.2014, 20:11. Показов 18116. Ответов 31
Метки нет (Все метки)

Сложение и вычитание
Имя входного файла: evalpm.in
Имя выходного файла: evalpm.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мебибайт

Выведите значение заданного арифметического выражения, состоящего из чисел, скобок и знаков сложения и вычитания.

Формат входных данных

В первой строке входного файла задано выражение, состоящее из чисел, скобок и знаков бинарных операций. Каждое число в выражении — это целое неотрицательное число в промежутке от 0 до 10000, включительно, записанное без ведущих нулей. Скобки бывают открывающие (`(') и закрывающие (`)'). Операции задаются символами `+' и `-'. Гарантируется, что заданное выражение математически корректно, и результаты всех промежуточных операций — целые числа, не превышающие по модулю 10000. Выражение не содержит каких-либо других символов, в частности, пробелов. Длина выражения не меньше 1 и не больше 1000 символов
Учтите, что операции при отсутствии скобок выполняются слева направо. Например, выражение a - b - c вычисляется как (a - b) - c.

Формат выходных данных

В первой строке выходного файла выведите одно число — значение заданного выражения.

Примеры

evalpm.in evalpm.out
48-13 35
5-(52+3) -50

Добавлено через 48 минут
Я придумал такой алгоритм. Сохранить арифметическое выражение в массив символов, запоминая при этом позиции открывающихся и закрывающихся скобок. Потом начать вычисления с самой правой открывающей скобки до закрывающей скобки. Затем пойти налево и сосчитать все выражения в скобках. Ну а потом уже сосчитать выражения без скобок.
Только я не представляю, как идентифицировать знаки '+' и '-', да и к тому же надо как-то конвертировать символы в числа, как это сделать я не понимаю и не воображаю...

Добавлено через 14 минут
Вот начало:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
 
#define LIM 1001        /* максимальное число элементов в массиве */
 
int main()
{
    int c, i, j, k;
    char str[LIM];      /* массив для хранения арифметического выражения */
    char pos1[LIM];     /* массив для хранения позиций открывающих скобок */
    char pos2[LIM];     /* массив для хранения позиций закрывающих скобок */
    
    i = j = k = 0;
    while ( ( str[i] = getchar() ) != '\n' ) {
        if ( str[i] == '(' )
            pos1[j++] = i;
        else
            if ( str[i] == ')' )
                pos2[k++] = i;
        i++;
    }
    return 0;
}
Осталось придумать ещё кучу кода

Добавлено через 19 минут
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
#include <stdio.h>
 
#define LIM 1001        /* максимальное число элементов в массиве */
 
int main()
{
    int c, i, j, k;
    char str[LIM];      /* массив для хранения арифметического выражения */
    char pos1[LIM];     /* массив для хранения позиций открывающих скобок */
    char pos2[LIM];     /* массив для хранения позиций закрывающих скобок */
    
    i = j = k = 0;
    while ((str[i] = getchar()) != '\n') {
        if ( str[i] == '(' )
            pos1[j++] = i;
        else
            if ( str[i] == ')' )
                pos2[k++] = i;
        i++;
    }
    str[i] = pos1[j] = pos2[k] = '\0';
    
    int sum = 0;
    j = k = 0;
    for (i = pos1[j]; pos1[j] != '\0' && pos2[k] != '\0'; j++, k++)
        /* здесь нужно вычислять значения в скобках, т. е. между pos1[j] и pos2[k]
        и присваивать их в переменную sum
        sum += выражение между pos1[j] и pos2[k], но пробелема в том, что даже
        функция atoi() не сможет вычленить числа из разных элементов массива */;
    return 0;
}
0
Лучшие ответы (1)
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
05.11.2014, 20:11
Ответы с готовыми решениями:

Напишите программу, которая вычисляет выражение, состоящее из трех чисел и двух знаков
Напишите программу, которая вычисляет выражение, состоящее из трех чисел и двух знаков (допускаются только знаки «+» или «–»). Выражение...

Напишите программу, которая вычисляет выражение, состоящее из чисел, знаков (допускаются знаки «+», «–», «*» и
Напишите программу, которая вычисляет выражение, состоящее из чисел, знаков (допускаются знаки «+», «–», «*» и «/») и круглых скобок....

Распарсить арифметическое выражение и вывести результат
добрый день, нужно написать программу, на ввод которой посылается математическое выражение (например:&quot;4*(5-2/3)&quot;)а на выводе...

31
2838 / 1647 / 254
Регистрация: 03.12.2007
Сообщений: 4,222
07.11.2014, 17:02
По моим наблюдениям, в олимпиадных задачах неаккуратный ввод/вывод относительно часто становится узким местом, так что, как минимум, sync_with_stdio false желательно ещё делать.

Добавлено через 2 минуты
И, кстати, когда из операций только "+" и "-", их можно считать знаками чисел, так что можно вообще парсить только числа и скобки.
0
Эксперт С++
 Аватар для Mr.X
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
07.11.2014, 18:11
Цитата Сообщение от Somebody Посмотреть сообщение
можно вообще парсить только числа и скобки
Можно было бы, если бы знак операции не мог стоять перед скобкой.
1
 Аватар для Dennis Ritchie
555 / 148 / 58
Регистрация: 27.07.2014
Сообщений: 2,446
07.11.2014, 18:41  [ТС]
Цитата Сообщение от Гоблин-инженер Посмотреть сообщение
Спорить не буду. Ваше мнение услышал, но останусь при своём.
Хорошо. Но теперь каждый раз, когда вы будете печатать "endl", вы будете вспоминать, что он работает медленнее, чем "\n"
Цитата Сообщение от Somebody Посмотреть сообщение
sync_with_stdio false желательно ещё делать.
Да, так тоже делают...
0
117 / 114 / 65
Регистрация: 18.09.2014
Сообщений: 337
07.11.2014, 18:44
Dennis Ritchie, обязательно как-нибудь вспомню. Даже запишу, а то вдруг (НЕ ДАЙ БОХ) забуду повспоминать
0
 Аватар для Dennis Ritchie
555 / 148 / 58
Регистрация: 27.07.2014
Сообщений: 2,446
07.11.2014, 18:50  [ТС]
Цитата Сообщение от Гоблин-инженер Посмотреть сообщение
Dennis Ritchie, обязательно как-нибудь вспомню. Даже запишу, а то вдруг (НЕ ДАЙ БОХ) забуду повспоминать
Тогда запишите ещё это:
ios_base::sync_with_stdio(0)
0
117 / 114 / 65
Регистрация: 18.09.2014
Сообщений: 337
07.11.2014, 18:56
Dennis Ritchie, обязательно. Ну, а вы, как ярый сторонник производительности, отправляйтесь зубрить ассемблер. А то какие-то программы небыстрые у вас получаются
0
 Аватар для Dennis Ritchie
555 / 148 / 58
Регистрация: 27.07.2014
Сообщений: 2,446
07.11.2014, 19:00  [ТС]
Цитата Сообщение от Гоблин-инженер Посмотреть сообщение
Ну, а вы, как ярый сторонник производительности, отправляйтесь зубрить ассемблер.
А asm не поддерживается тестирующей системой, так что не выйдет. Потом, конечно, изучу, чтобы делать вставки в код C++
0
117 / 114 / 65
Регистрация: 18.09.2014
Сообщений: 337
07.11.2014, 19:03
Dennis Ritchie, тоже медленно. Выбросьте вообще эти медленные языки, чистый ассемблер, трестирующую систему тоже на ассемблере напишите. Думаю, тогда вы будете полностью довольны производительностью. Мне же хватает производительности и с использованием этих "жутко медленных" endl
0
 Аватар для Dennis Ritchie
555 / 148 / 58
Регистрация: 27.07.2014
Сообщений: 2,446
07.11.2014, 19:08  [ТС]
Цитата Сообщение от Гоблин-инженер Посмотреть сообщение
Мне же хватает производительности и с использованием этих "жутко медленных" endl
Хорошо, тогда я перепишу код всех компиляторов, введу стандарт C++17. И в итоге вы не сможете использовать "endl", "cin" и "cout", замедляющий работоспособность программ в 4,5 раза.
0
117 / 114 / 65
Регистрация: 18.09.2014
Сообщений: 337
07.11.2014, 19:12
Dennis Ritchie, ну бегите, пишите...
0
 Аватар для Dennis Ritchie
555 / 148 / 58
Регистрация: 27.07.2014
Сообщений: 2,446
07.11.2014, 19:13  [ТС]
Цитата Сообщение от Гоблин-инженер Посмотреть сообщение
Dennis Ritchie, ну бегите, пишите...
До 2017 года много времени. Мне некуда торопиться.
0
 Аватар для Dennis Ritchie
555 / 148 / 58
Регистрация: 27.07.2014
Сообщений: 2,446
14.11.2014, 01:49  [ТС]
Реализация обратной польской записи со стеком из книги Кернигана и Ритчи

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
#include <stdio.h>
#include <stdlib.h>     /* для объявления atof() */
 
#define MAXOP   100     /* максимальный размер операнда или знака */
#define NUMBER '0'      /* сигнал, что обнаружено число */
 
int getop(char s[]);
void push(double);
double pop(void);
 
/* калькулятор с обратной польской записью */
int main()
{
    int type;
    double op2;
    char s[MAXOP];
 
    while ((type = getop(s)) != EOF) {
        switch(type) {
        case NUMBER:
            push(atof(s));
            break;
        case '+':
            push(pop() + pop());
            break;
        case '*':
            push(pop() * pop());
            break;
        case '-':
            op2 = pop();
            push(pop() - op2);
            break;
        case '/':
            op2 = pop();
            if (op2 != 0.0)
                push(pop() / op2);
            else
                printf("error: zero divisor\n");
            break;
        case '\n':
            printf("\t%.8g\n", pop());
            break;
        default:
            printf("error: unknown command %s\n", s);
            break;
        }
    }
    return 0;
}
 
#define MAXVAL  100     /* максимальная глубина стека val */
 
int sp = 0;             /* следующая свободная позиция в стеке */
double val[MAXVAL];     /* стек операндов */
 
/* push: помещает число f в стек операндов */
void push(double f)
{
    if (sp < MAXVAL)
        val[sp++] = f;
    else
        printf("error: stack full, can't push %g\n", f);
}
 
/* pop: извлекает и возвращает верхнее число из стека */
double pop(void)
{
    if (sp > 0)
        return val[--sp];
    else {
        printf("error: stack empty\n");
        return 0.0;
    }
}
 
#include <ctype.h>
 
int getch(void);
void ungetch(int);
 
/* getop: извлекает следующий операнд или знак операции */
int getop(char s[])
{
    int i, c;
    
    while ((s[0] = c = getch()) == ' ' || c == '\t')
        ;
    s[1] = '\0';
    if (!isdigit(c) && c != '.')
        return c;       /* не число */
    i = 0;
    if (isdigit(c))     /* накопление целой части */
        while (isdigit(s[++i] = c = getch()))
            ;
    if (c == '.')   /* накопление дробной части */
        while (isdigit(s[++i] = c = getch()))
            ;
    s[i] = '\0';
    if (c != EOF)
        ungetch(c);
    return NUMBER;
}
 
#define BUFSIZE 100
 
char buf[BUFSIZE];  /* буфер для ungetch */
int bufp = 0;       /* следующая свободная позиция в buf */
 
int getch(void) /* ввод символа (возможно, возвращённого в поток) */
{
    return (bufp > 0) ? buf[--bufp] : getchar();
}
 
void ungetch(int c) /* возвращение символа в поток ввода */
{
    if (bufp >= BUFSIZE)
        printf("ungetch: too many characters\n");
    else
        buf[bufp++] = c;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
14.11.2014, 01:49

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

Вычислить выражение, состоящее из трех чисел и двух знаков
Напишите программу, которая вычисляет выражение, состоящее из трех чисел и двух знаков (допускаются знаки «+», «–», «*» и «/»). Выражение...

Напишите программу, которая вычисляет выражение, состоящее из трех чисел и двух знаков
Pascal ABC Буду очень благодарен, если поможете с решением программы) вот само задание: &quot;Напишите программу, которая вычисляет...

Напишите программу, которая вычисляет выражение, состоящее из трех чисел и двух знаков
Напишите программу, которая вычисляет выражение, состоящее из трех чисел и двух знаков (допускаются только знаки «+» или «–»). Выражение...

Напишите программу, которая вычисляет выражение, состоящее из трех чисел и двух знаков (допускаются знаки «+», «–», «*» и «/»)
Здравствуйте. Прошу помощи. Уровень C. Напишите программу, которая вычисляет выражение, состоящее из трех чисел и двух знаков...


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

Или воспользуйтесь поиском по форуму:
32
Ответ Создать тему
Новые блоги и статьи
[golang] Конкурентный fetcher с ограничением максимального количества одновременных HTTP запросов.
alhaos 10.06.2026
Задача Реализовать конкурентный fetcher с ограничением максимального количества одновременных HTTP запросов. Сигнатура func Fetch(urls string, maxConcurrent int) Result Пример urls :=. . .
[golang] Состояние гонки (race condition)
alhaos 10.06.2026
Состояние гонки (race condition) Состояние гонки (Race Condition) — это ошибка, возникающая при одновременном доступе нескольких горутин к одним и тем же данным без должной синхронизации. При этом. . .
Взрослые отношения, и почему они не получаются
kumehtar 09.06.2026
Когда в детстве ребёнок не получает от родителей чего-то важного, он лишается не просто приятных переживаний, а основы для формирования определённых внутренних качеств и навыков. Если ребёнок не. . .
[golang] Worker Pool
alhaos 09.06.2026
Worker Pool Worker Pool — паттерн конкурентной обработки задач в Go. Суть: фиксированное количество горутин-воркеров читают задачи из общего канала и пишут результаты в общий канал результатов. . . .
[golang] Pipeline
alhaos 08.06.2026
Pipeline Pipeline — паттерн конкурентной обработки данных в Go. Суть: данные проходят через цепочку независимых стадий, каждая из которых работает в своей горутине и общается с соседями через. . .
Свет внутри себя
kumehtar 07.06.2026
Пусть это будет здесь lIs4oanZS9Y
Программа для com-порта
Uhbif79 05.06.2026
Всем привет, давно хотел изучить Qt, начинал, бросал, потом снова начинал. И сейчас вот смог написать свою первую программу. До этого имел опыт программирования микроконтроллеров, писал прошивки на. . .
Транскрипция 55-минутного видео через Whisper: WhisperDesktop облажался, спас Google Colab[
anaschu 01.06.2026
Понадобилось получить текст из свежезагруженного видео на YouTube. Казалось бы, задача на пять минут. Заняла полтора часа. Делюсь опытом — может кому пригодится последовательность решений. . . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru