powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Убрать скобки в выражении
11 сообщений из 11, страница 1 из 1
Убрать скобки в выражении
    #35667355
foxwizard
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Может кто сталкивался.
Нужен алгоритм, убирающий скобки а выражениях.
на входе строки, например
1. ((tax1+cost*count)+d)
2. (a+b)+(c+d) +e(f+g)
и.т.д.
Нужено упростить выражение- убрать незначащие скобки.
получить для
1. ((tax1+cost*count)+d)=tax1+cost*count+d
2. (a+b)+(c+d) +e(f+g)=a+b+c+d +e(f+g)
...
Рейтинг: 0 / 0
Убрать скобки в выражении
    #35667532
retty_jj
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
типа так?

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
Sample Input:

 8 
(a+(b*c))
((a+b)*c)
(a*(b*c))
(a*(b/c)*d)
((a/(b/c))/d)
((x))
(a+b)-(c-d)-(e/f)
(a+b)+(c-d)-(e+f)


Sample Output:

a+b*c
(a+b)*c
a*b*c
a*b/c*d
a/(b/c)/d
x
a+b-(c-d)-e/f
a+b+c-d-(e+f)


у меня вроде бы есть готовое, тока для однобуквенных переменных (что не проблема)
...
Рейтинг: 0 / 0
Убрать скобки в выражении
    #35667546
foxwizard
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Взглянуть можно ?
...
Рейтинг: 0 / 0
Убрать скобки в выражении
    #35667659
jsXYZ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
поиск "Обратная польская запись"
...
Рейтинг: 0 / 0
Убрать скобки в выражении
    #35667678
foxwizard
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ОПЗ не проходит.
Да, скобок там нет, но приоритеты остаются теже. Что при построении дерева разбора мне не нужно.
Мне надо убрать лишние скобки.
...
Рейтинг: 0 / 0
Убрать скобки в выражении
    #35667873
retty_jj
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
foxwizardОПЗ не проходит.
Да, скобок там нет, но приоритеты остаются теже. Что при построении дерева разбора мне не нужно.
Мне надо убрать лишние скобки.
у меня вроде на паскале... пойдет? (саму идею алгоритма надо вспоминать)
...
Рейтинг: 0 / 0
Убрать скобки в выражении
    #35667878
foxwizard
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
конечно!
...
Рейтинг: 0 / 0
Убрать скобки в выражении
    #35668225
retty_jj
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Это я когда-то делал вот под эту таску: http://www.spoj.pl/problems/CMEXPR/
Код корректен на 100%. В принципе, он не чувствителен к "многобуквенности" переменных, но кое-где затыкается

Например на ((a+www)/(uuu)). Выдает (a+www)/(uuu). Если всё односимвольно, то Ок.

Где надо поправить вижу, но как слету не соображу

Код: plaintext
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.
{$APPTYPE CONSOLE}

var
    n, i, j, sch: longint;
    fl: boolean;
    a, b: ansistring;
    h, g: array[ 0 .. 5555 ] of longint;


procedure del_pair(i: longint);
    begin
        b[i] := '#';
        b[h[i]] := '#';
        a[i] := a[i- 1 ];
        a[h[i]] := a[h[i]+ 1 ];
    end;



begin
repeat

readln(a);

n := length(a);

a := '#' + a + '#';

b := a;

sch :=  0 ;

for i :=  2  to n +  1  do
    if a[i] = '(' then
        begin
            inc(sch);
            g[sch] := i;
        end
    else
    if a[i] = ')' then
        begin
            h[g[sch]] := i;
            dec(sch);
        end;


for i :=  2  to n +  1  do
    if a[i] = '(' then
        begin
            if ((a[i+ 1 ] = '(') and (h[i+ 1 ] = h[i] -  1 )) or (i +  2  = h[i]) then
                begin
                    del_pair(i);
                    continue;
                end;

            if a[i- 1 ] = '/' then continue;

            if (a[i- 1 ] in ['+', '#', '(']) and (not(a[h[i]+ 1 ] in ['/', '*'])) then
                begin
                    del_pair(i);
                    continue;
                end;

        fl := true;
        sch :=  0 ;

        for j := i +  1  to h[i] -  1  do
            if ((a[j] = '+') or (a[j] = '-')) and (sch =  0 ) then
                begin
                    fl := false;
                    break;
                end
            else
            if a[j] = '(' then inc(sch)
            else
            if a[j] = ')' then dec(sch);
        if fl then
            begin
                del_pair(i);
                continue;
            end;

        end;



for i :=  2  to n +  1  do
    if b[i] <> '#' then write(b[i]);
writeln;


until false;
end.
...
Рейтинг: 0 / 0
Убрать скобки в выражении
    #35668280
foxwizard
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Спасибо
...
Рейтинг: 0 / 0
Убрать скобки в выражении
    #35668717
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
foxwizard пишет:
> Может кто сталкивался.
> Нужен алгоритм, убирающий скобки а выражениях.
> на входе строки, например

Можно порекомендовать более общий алгоритм - алгоритм Дейкстры
по переводу в обратную польскую запись. На algorithm.ru кажется он есть.
Потом восстановить выражение с минимальными скобками по обратной
польской записи не сложно.
Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
Убрать скобки в выражении
    #35668922
retty_jj
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
MasterZiv
На algorithm.ru кажется он есть.


да там собсно и алгоритма как бы нет :)

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
tcs = input()

for tc in range(tcs):
    s = raw_input()
    st = []
    ss = ''
    for i in s:
        if 'a' <= i <= 'z':
            ss += i
        elif i == ')':
            while not(st[- 1 ] == '('):
                ss += st.pop()
            st.pop()
        else:
            st.append(i)
    if st:
        ss += st.pop()
    print ss

Под эту:

spoj
SPOJ Problem Set
4. Transform the Expression
Problem code: ONP

Transform the algebraic expression with brackets into RPN form (Reverse Polish Notation).
Two-argument operators: +, -, *, /, ^ (priority from the lowest to the highest), brackets ( ).
Operands:
only letters: a,b,...,z. Assume that there is only one RPN form (no expressions like a*b*c).

Input

t [the number of expressions <= 100]
expression [length <= 400]
[other expressions]
Text grouped in [ ] does not appear in the input file.

Output

The expressions in RPN form, one per line.


Example

Input:

3
(a+(b*c))
((a+b)*(z+x))
((a+t)*((b+(a+c))^(c+d)))



Output:

abc*+
ab+zx+*
at+bac++cd+^*
...
Рейтинг: 0 / 0
11 сообщений из 11, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Убрать скобки в выражении
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]