Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Убрать скобки в выражении / 11 сообщений из 11, страница 1 из 1
21.11.2008, 10:50:41
    #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
21.11.2008, 11:37:45
    #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
21.11.2008, 11:40:58
    #35667546
foxwizard
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Убрать скобки в выражении
Взглянуть можно ?
...
Рейтинг: 0 / 0
21.11.2008, 12:09:07
    #35667659
jsXYZ
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Убрать скобки в выражении
поиск "Обратная польская запись"
...
Рейтинг: 0 / 0
21.11.2008, 12:13:12
    #35667678
foxwizard
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Убрать скобки в выражении
ОПЗ не проходит.
Да, скобок там нет, но приоритеты остаются теже. Что при построении дерева разбора мне не нужно.
Мне надо убрать лишние скобки.
...
Рейтинг: 0 / 0
21.11.2008, 12:58:50
    #35667873
retty_jj
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Убрать скобки в выражении
foxwizardОПЗ не проходит.
Да, скобок там нет, но приоритеты остаются теже. Что при построении дерева разбора мне не нужно.
Мне надо убрать лишние скобки.
у меня вроде на паскале... пойдет? (саму идею алгоритма надо вспоминать)
...
Рейтинг: 0 / 0
21.11.2008, 13:00:21
    #35667878
foxwizard
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Убрать скобки в выражении
конечно!
...
Рейтинг: 0 / 0
21.11.2008, 14:34:04
    #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
21.11.2008, 14:47:12
    #35668280
foxwizard
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Убрать скобки в выражении
Спасибо
...
Рейтинг: 0 / 0
21.11.2008, 16:41:55
    #35668717
MasterZiv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Убрать скобки в выражении
foxwizard пишет:
> Может кто сталкивался.
> Нужен алгоритм, убирающий скобки а выражениях.
> на входе строки, например

Можно порекомендовать более общий алгоритм - алгоритм Дейкстры
по переводу в обратную польскую запись. На algorithm.ru кажется он есть.
Потом восстановить выражение с минимальными скобками по обратной
польской записи не сложно.
Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
21.11.2008, 18:04:44
    #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]