# Problema Bracketswap

**URL:** <https://forum.olinfo.it/t/problema-bracketswap/8788>\
**Category:** Aiuto\
**Created:** [11 Marzo 2024, 4:57pm UTC](https://forum.olinfo.it/t/problema-bracketswap/8788 "2024-03-11T16:57:47Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![info\_c](https://forum.olinfo.it/user_avatar/forum.olinfo.it/info_c/32/2345_2.png) [@info\_c](https://forum.olinfo.it/u/info_c)\
**Post date:** [11 Marzo 2024, 4:57pm UTC](https://forum.olinfo.it/t/problema-bracketswap/8788/1 "2024-03-11T16:57:47Z")

</div>

Ho provato a svolgere Bracketswap e ottengo 0/100 perchè tutti i testcase (esclusi quelli di esempio e il 4) sono errati.  
La risoluzione ricalca altri esercizi simili sul bilanciamento di parentesi, quindi mi aspetterei almeno qualche testcase corretto.  
Non credo sia un errore di lettura dell’input perchè i casi di esempio sono corretti e quello che ha una espressione bilanciata in ingresso la riconosce.  
Sarebbe utile avere uno o più esempi di testcase. Se possibile. Grazie.

---

<div class="post-metadata">

**Author:** ![v.bizzarri](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/v/7c8e57/32.png) [@v.bizzarri](https://forum.olinfo.it/u/v.bizzarri)\
**Post date:** [12 Marzo 2024, 9:03am UTC](https://forum.olinfo.it/t/problema-bracketswap/8788/2 "2024-03-12T09:03:07Z")

</div>

Se non posti il tuo codice difficile proporti esempi nei quali il tuo codice non va.

---

<div class="post-metadata">

**Author:** ![info\_c](https://forum.olinfo.it/user_avatar/forum.olinfo.it/info_c/32/2345_2.png) [@info\_c](https://forum.olinfo.it/u/info_c)\
**Post date:** [12 Marzo 2024, 9:52am UTC](https://forum.olinfo.it/t/problema-bracketswap/8788/3 "2024-03-12T09:52:55Z")

</div>

Grazie per la risposta.  
Il codice è in Pascal, ho messo dei commenti alle righe di codice.

```auto
program bracketswap;
const MAXN=1000010;
var
    N, R, i,j, h,w, pos, pos1, scambi, lungh: LongInt;
    ST:ansistring;
    S: array[0..MAXN] of char;
    S1: array[-1..MAXN] of char;
    idopen, idclose :array[0..MAXN] of longint;
    p:char;
begin
    assign(input, 'input.txt'); reset(input);
    assign(output, 'output.txt'); rewrite(output);
    ReadLn(N);
    for i:=0 to N-1 do read(S[i]); 
    readln;
    (*uso due array per memorizzare la posizione iniziale delle parentesi aperte e chiuse nella espressione*)
    for i:=0 to N-1 do begin idopen[i]:=0; idclose[i]:=0; end;
    (*leggo e verifico se è bilanciata e tolgo la parte bilanciata*)
    pos1:=-1; 
    pos:=-1; 
    h:=0; j:=0; lungh:=N; 
    while (pos <lungh-1) do
      begin
        pos:=pos+1;
        p:=S[pos];
        if p='(' then 
                         begin
                            pos1:=pos1+1;
                            S1[pos1]:=p;
                            idopen[h]:=pos;
                            h:=h+1;
                        end   
                    else
                       if ( p=')') then begin if (pos1>=0) and (S1[pos1]='(') then begin pos1:=pos1-1;h:=h-1; end  
                                                                              else begin pos1:=pos1+1; S1[pos1]:=p; idclose[j]:=pos; j:=j+1;end;
                                        end;
      end;
      (*quello che rimane sono parentesi non bilanciate metà delle quali chiuse e metà aperte*)
      lungh:=pos1+1; 
      R:=lungh div 2;
      (*calcolo il numero di scambi*)
      if R mod 2 = 0 then scambi:= R div 2
                     else scambi:=(R+1) div 2;
      writeln (scambi);
      w:=0;
      while w<scambi do begin writeln(idclose[0+w],' ',idopen[R-1-w]); w:=w+1; end;
  end.

```

---

<div class="post-metadata">

**Author:** ![fve5](https://forum.olinfo.it/user_avatar/forum.olinfo.it/fve5/32/3229_2.png) [@fve5](https://forum.olinfo.it/u/fve5)\
**Post date:** [12 Marzo 2024, 12:25pm UTC](https://forum.olinfo.it/t/problema-bracketswap/8788/4 "2024-03-12T12:25:07Z")

</div>

Non ci credo, finalmente la mia macchina del tempo funziona!

> **P.S.**
>
> C’è qualche motivo particolare per cui usi Pascal? Sono molto curioso.

---

<div class="post-metadata">

**Author:** ![info\_c](https://forum.olinfo.it/user_avatar/forum.olinfo.it/info_c/32/2345_2.png) [@info\_c](https://forum.olinfo.it/u/info_c)\
**Post date:** [12 Marzo 2024, 6:15pm UTC](https://forum.olinfo.it/t/problema-bracketswap/8788/5 "2024-03-12T18:15:36Z")

</div>

Ho fatto una domanda obsoleta ::  
Non conosco in modo adeguato il C++ e quindi ho utilizzato il Pascal per me più confortevole.  
Ogni tanto leggo con interesse i contenuti di questo forum e provo a svolgere qualche esercizio, ma l’esito di questa sottoposizione non riesco a spiegarlo.  
Se la causa di errore è indipendente dal linguaggio di programmazione, ma dipende dalla logica di soluzione, potrebbe essere comunque utile, in caso contrario mi scuso per la domanda.

---

<div class="post-metadata">

**Author:** ![v.bizzarri](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/v/7c8e57/32.png) [@v.bizzarri](https://forum.olinfo.it/u/v.bizzarri)\
**Post date:** [12 Marzo 2024, 9:04pm UTC](https://forum.olinfo.it/t/problema-bracketswap/8788/6 "2024-03-12T21:04:44Z")

</div>

prova con  
16  
(()))())))(((()(

---

<div class="post-metadata">

**Author:** ![info\_c](https://forum.olinfo.it/user_avatar/forum.olinfo.it/info_c/32/2345_2.png) [@info\_c](https://forum.olinfo.it/u/info_c)\
**Post date:** [18 Marzo 2024, 9:14pm UTC](https://forum.olinfo.it/t/problema-bracketswap/8788/7 "2024-03-18T21:14:02Z")

</div>

Grazie.  
Ottengo come output  
2  
4 15  
7 12  
Con questi due scambi l’espressione diventa bilanciata.  
Ma è corretto?

---

<div class="post-metadata">

**Author:** ![v.bizzarri](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/v/7c8e57/32.png) [@v.bizzarri](https://forum.olinfo.it/u/v.bizzarri)\
**Post date:** [19 Marzo 2024, 11:55am UTC](https://forum.olinfo.it/t/problema-bracketswap/8788/8 "2024-03-19T11:55:00Z")

</div>

Non so molto di Pascal ma probabilmente c’è un problema di lettura dei dati: se metto uno spazio all’inizio della riga con le parentesi mi pare che il tuo programma non funzioni mentre il mio programma in C++ funziona. Togliendo lo spazio mi pare funzioni anche i tuo.  
Prova a leggere l’intera sequenza di caratteri come stringa (e trimmandola)  
prova di nuovo con  
16  
(()))())))(((()(  
C’è uno spazio prima della prima parentesi.

---

<div class="post-metadata">

**Author:** ![info\_c](https://forum.olinfo.it/user_avatar/forum.olinfo.it/info_c/32/2345_2.png) [@info\_c](https://forum.olinfo.it/u/info_c)\
**Post date:** [19 Marzo 2024, 8:57pm UTC](https://forum.olinfo.it/t/problema-bracketswap/8788/9 "2024-03-19T20:57:21Z")

</div>

Grazie!  
Era effettivamente un errore di lettura dei dati.  
Usando TrimLeft(stringa) ha letto correttamente l’input.