Аватар для Dennis Ritchie
555 / 148 / 58
Регистрация: 27.07.2014
Сообщений: 2,446

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

05.11.2014, 20:11. Показов 18218. Ответов 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
Ответ Создать тему
Опции темы

Новые блоги и статьи
Кредитный калькулятор
Maks 05.08.2026
Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .
У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35".
kumehtar 04.08.2026
С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .
Как ИИ начал спорить и врать (возможно почуяв опасность для себя от индустрии - уход от электроники).
Hrethgir 04.08.2026
Недельный диалог, на фоне событий с НПЗ. Да, из спирта можно получать бензин, и это не сложно. Но потом в схеме я решил избавиться от насоса, при этом полностью сделав контроль подачи спирта в. . .
Термопринтер QR701
Argus19 03.08.2026
Термопринтер QR701 Купил два термопринтера QR701. На сэлф-тесте написано: Language: PC936 (GB18030). Что означает, что принтеры могут печатать только латиницу и китайские иероглифы. Так же. . .
Создание формы заимствованного документа
Maks 03.08.2026
Задача: Необходимо создать собственную форму заимствованного документа. На форме должен быть реквизит "Покупатель", а также табличная часть со следующими реквизитами: - Расчетный счет покупателя. . .
Задача предоставления скидок покупателям
Maks 03.08.2026
Задача: В документе "Продажи" необходимо реализовать функционал предоставления скидок покупателям. Скидка должна автоматически рассчитываться и подставляться в соответствующее поле при выборе. . .
Почему SEO не начинается с ключевых слов: что проверить до написания текстов
Neotwalker 01.08.2026
Когда владельцу сайта предлагают заняться SEO, первым шагом часто становится сбор запросов и написание текстов. Логика кажется понятной: 1. Находим ключевые слова. 2. Добавляем их на. . .
Знание — сила: Доктрина интенциональности знаний, углубление в формулу
Hrethgir 01.08.2026
https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11957&stc=1&d=1785567302 Знаменитый афоризм Фрэнсиса Бэкона «Знание — сила» (Scientia potentia est) в массовой культуре принято понимать. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru