C# - Kontrollera om parenteser är balanserade

Citera flera Citera

2015-05-25 15:03

Dunder

Keeper of Traditions ★

Plats: Bästkusten
Registrerad: Jun 2009

●

Klistra in din kod så man kan se hur långt du kommit och visa vart du har fastnat. Som du säkert förstår kommer inte andra göra dina läxor åt dig.

Enkel stränghantering och ett par if-satser bör vara tillräckligt om det endast är de givna exemplen du behöver hantera.

EDIT: T.ex:

if(string[i].equals("(") && !string[i+1].equals(")")
{
      print("error")
}

EDIT2: Det ska tilläggas att jag inte kommer ihåg korrekt C#-syntax.

Senast redigerat 2015-05-25 15:18

Visa signatur

|| Intel 8700K || Asus RTX 4070 TI Super TUF || Samsung 750 EVO 500GB & Kingston A2000 1TB & Samsung 960 EVO 250GB || Corsair RM 850x || Antec P183 || Asus G-Sync RoG Swift PG279Q || Dell XPS 15 || Thinkpad X220

The Force is like Duct Tape, it has a light side, a dark side, and holds the universe together.

Citera flera Citera

2015-05-25 15:21

lassep1l1s

Medlem ★

Registrerad: Sep 2006

●

Rör det sig kanske snarare om parentes-balansering i kod?
Undvika strängar som kan innehålla en parentes och kommentarer som kan innehålla en smily.

Citera flera Citera

2015-05-25 15:25

Biberu

Legendarisk ★

Hedersmedlem

Registrerad: Dec 2002

●

Skrivet av Lamposksk:

Källkodskontroll: Skriv ett program som kontrollerar att en källkodsfil är korrekt med avseende på () parenteser. Exempel på korrekta parentesföljder är ()() och (()) och exempel på felaktig är )( och ())().

Uppgiften är att kontrollera om strängen innehåller balanserade parenteser; det vill säga att för varje öppning så måste det finnas en stängning, du kan inte stänga något du inte har öppnat och när du når strängens slut ska det inte finnas några kvarvarande öppningar. Det är ett vanligt stackproblem, om din bok har nämnt det ordet så kan du antagligen få en ledtråd till hur det kan implementeras där.

Visa signatur

Abstractions all the way down.

Citera flera Citera (2)

2015-05-25 15:41

Tetratrio

Medlem

Plats: Lund
Registrerad: Jan 2014

●

Länge sedan jag satt i C# men här är ett exempel på en lösning!

String text = .....

int balance = 0;
foreach (char c in text) {
    if (c == '(') {
        balance++;
    }
    else if (c == ')') {
        balance--;
    }
    if (balance < 0) {
        //Fel på paranteser. Stängande parantes kom innan öppnande.
    }
}

if (balance != 0) {
    //Fel på paranteser. balance > 0 ger för många öpnnande paranteser. balance < 0 ger för många stängande.
}

Visa signatur

i7-7800x | ASUS Strix GTX 1080 | 64 GB RAM (for datascience stuff)

Citera flera Citera (2)

2015-05-25 18:45

Lamposksk

Medlem

Registrerad: Maj 2015

●

@Tetratrio: Tjo, tack men såg att jag skulle använda mig av en stack. Vilket är helt rövat. =&

Citera flera Citera

2015-05-25 19:14

lassep1l1s

Medlem ★

Registrerad: Sep 2006

●

@Tetratrio
Snygg lösning. Något som jag i nästan 30 år i S/W-träsket funderade på. Om bara koden ska kollas måste strängar (meddelanden) och kommentarer uteslutas.
Redan -87 hade NE (Norton Editor i DOS) parantes och klammer-balansering.
Sannolikt måste mer än en rad i koden analyseras.

Citera flera Citera

2015-05-25 19:33

Lamposksk

Medlem

Registrerad: Maj 2015

●

@Dunder:

namespace Källkodskontroll
{
    public partial class Form1 : Form
    {
        Stack<char> Källkod = new Stack<char>();

        public Form1()
        {
            InitializeComponent();
        }

        private void btnKontrollera_Click(object sender, EventArgs e)
        {
            string Parentes = tbxParentes.Text;

            char[] allowedChars = { '(', ')' };

            foreach (char A in Parentes)
            {
                if (Parentes == "(")
                {
                    Källkod.Push(A);
                }

                if (Parentes == ")" )
                {
                    if (Källkod.Last() == '(')
                    {
                        Källkod.Pop();
                    }
                    else
                    {
                        Källkod .Push(A);
                    }
                }
            }
            while (Parentes != "");
        }
    }
}

Programmet fryser sig, vet inte om jag gjort helt fel eller om det är något litet fel.

Citera flera Citera

2015-05-25 19:39

anon81912

Inaktiv

Registrerad: Feb 2006

●

Skrivet av Lamposksk:

@Tetratrio: Tjo, tack men såg att jag skulle använda mig av en stack. Vilket är helt rövat. =&

Vet du hur en stack fungerar blir det väldigt enkelt, vet du inte det blir det något du kan lära dig

Tänk dig att din stack har följande funktioner:
POP (tar bort och hämtar senaste elementet)
PEEK (tittar på det element du lagt senast)
PUSH (lägger ett element på stacken)

Då kan man tänka sig nåt sånhärt:

function checkIfBalanced(char[] text) {
	var stack = new Stack()
	foreach(char c in text){
		switch(c){
			case '(':
				stack.push(c);
				break;
			case ')':
				if(stack.peek().equals('(')))
					stack.pop();
				else //Obalanserat
					return false;
				break;
		}
	}

	//Är stacken tom är det balanserat
	return stack.isEmpty();
}

Citera flera Citera

2015-05-25 19:48

Biberu

Legendarisk ★

Hedersmedlem

Registrerad: Dec 2002

●

@Lamposksk: Om du indenterar/formaterar din kod så blir den lättare att arbeta med både för dig och de som försöker hjälpa till. Du kan även använda [code]...[/code]-taggar för att bevara formateringen när du postar kodsnuttar på forumet. Har förtydligat ditt inlägg lite.

Visa signatur

Abstractions all the way down.

Citera flera Citera

2015-05-25 19:49

Lamposksk

Medlem

Registrerad: Maj 2015

●

@anon81912: Ah, tack. Men jag använder Visual vilket är annorlunda? Tror ja? Så det blir redigt många errors. Är det sån skillnad eller har ja helt fel?

Citera flera Citera

2015-05-25 20:31

anon81912

Inaktiv

Registrerad: Feb 2006

●

Skrivet av Lamposksk:

@Killbom: Ah, tack. Men jag använder Visual vilket är annorlunda? Tror ja? Så det blir redigt många errors. Är det sån skillnad eller har ja helt fel?

Jag skrev sån kallad pseudokod. Poängen i detta fallet är att du inte skall kunna köra den. Du får själv titta på koden, förstå den och skriva en implementation. (Däremot skrev jag den ganska så likt C#)

Citera flera Citera (2)

2015-05-25 20:35

Lamposksk

Medlem

Registrerad: Maj 2015

●

@anon81912: Ah, okej. Försökte med en kod men det funkar inte, tips?

namespace Källkodskontroll
{
    public partial class Form1 : Form
    {
        Stack<char> Källkod = new Stack<char>();

        public Form1()
        {
            InitializeComponent();
        }

        private void btnKontrollera_Click(object sender, EventArgs e)
        {
            string Parentes = tbxParentes.Text;

            char[] allowedChars = { '(', ')' };

                 foreach (char A in Parentes)
            {
                if (Parentes == "(")
                {
                    Källkod.Push(A);
                }

                if (Parentes == ")" )
                {
                    if (Källkod.Last() == '(')
                    {
                        Källkod.Pop();
                    }
                    else
                    {
                        Källkod .Push(A);
                    }
                }            
                }
 
            while (Parentes != "") ;    
        }
        }
    }

Error:
Type or namespace definition, or end-of-file expected

Redigerat in [code]-taggar

Citera flera Citera

2015-05-25 20:47

Biberu

Legendarisk ★

Hedersmedlem

Registrerad: Dec 2002

●

@Lamposksk:

public partial class Form1 : Form
{
    A. Stack<char> Källkod = new Stack<char>();

    private void btnKontrollera_Click(object sender, EventArgs e)
    {
        string Parentes = tbxParentes.Text;

        B. char[] allowedChars = { '(', ')' };

        foreach (char A in Parentes)
        {
            C. if (Parentes == "(")
            {
                Källkod.Push(A);
            }

            D. if (Parentes == ")" )
            {
                E. if (Källkod.Last() == '(')
                {
                    Källkod.Pop();
                }
                else
                {
                    Källkod .Push(A);
                }
            }
        }
        F. while (Parentes != "");
        
        G. ?
    }
}

A.

Eftersom att du har deklarerat Källkod som en egenskap för varje instans av din klass så kommer dess tillstånd bevaras mellan anrop till btnKontrollera_Click(). Det vore bättre att hantera din stack / räknare inuti funktionens eget scope, på det sättet undviker du bland annat problem med att ha glömt rensa den. Vad händer om kör funktionen flera gånger nu?

B.

Listan deklareras, men används aldrig.

C., D.

Det är viktigt att namnge variabler ordentligt. Vid ett första ögonkast kan de här jämförelserna se rätt ut, men sedan märker vi att ")" är en sträng och inte en char, det kan inte stämma, och Parentes är ju hela din text och inte det aktuella tecknet A. Kan du hitta bättre namn för Källkod, Parentes, A?

E.

Eftersom att Källkod bara kan innehålla öppningsparenteser räcker det att kontrollera om den inte är tom; är den inte det så kan du ta bort ett element och fortsätta, annars vet du att parenteserna var obalanserade och kan avsluta uppgiften.

F.

Medans Parentes (hela din text) inte är en tom sträng fortsätt göra ingenting, det är därför ditt program verkar hänga sig. Har du ersatt en do/while med foreach och glömt den här raden?

G.

Vad ska du göra när du är klar? Hur vet du hur det gick?

Senast redigerat 2015-05-25 21:19

Visa signatur

Abstractions all the way down.

Citera flera Citera (1)

2015-05-25 21:10

Lamposksk

Medlem

Registrerad: Maj 2015

●

@Tunnelsork: Förstod ända tills E sen så fattade jag ingenting. :/

Måste väl göra om allt antar jag, ser inte rätt ut iaf. :s

Citera flera Citera

2015-05-25 21:48

anon81912

Inaktiv

Registrerad: Feb 2006

●

@Lamposksk:
Få rätt på dina parenteser för att lösa ditt fel.

Dessutom är själva logiken fel. Varför pushar du ')'?

public bool isBalanced(string text){
	bool isBalanced = false;
	var stack = new Stack<char>();

	foreach (char c in text.ToCharArray())
	{
		if(c == '(') {
			stack.Push(c);
		} else if(c== ')') {
			if(stack.Last() == '(')
				stack.Pop();
			else 
				return false;				
		}
	}
	
	return stack.Count == 0
}

Nu har jag inte testat, men skrev detta i notepad, så du har något att jämföra med?

Senast redigerat 2015-05-25 21:59

Citera flera Citera

2015-05-25 21:56

Lamposksk

Medlem

Registrerad: Maj 2015

●

@anon81912: Ingen aning... :S Fattar inte vad jag håller på med atm ens.

Vill försöka få ut när det är balanserade parenteser så ska de stå att det är balanserat eller ej, och det kan jag fixa lätt med labels, men sen så äre ju allt annat som man inte har en aning om.

Citera flera Citera

2015-05-25 21:58

anon81912

Inaktiv

Registrerad: Feb 2006

●

Skrivet av Lamposksk:

@Killbom: Ingen aning... :S Fattar inte vad jag håller på med atm ens.

Vill försöka få ut när det är balanserade parenteser så ska de stå att det är balanserat eller ej, och det kan jag fixa lätt med labels, men sen så äre ju allt annat som man inte har en aning om.

Kolla mitt förra inlägg.

Det är detta du vill göra, i en punktlista:
1. Plocka ut varje enskild bokstav i texten
2. Kolla om bokstaven är ( eller ), annars gå till nästa.
3. Om den är (, spara den på stacken
3. Om den är ), kolla om den har en kompis i stacken, annars är det fel
3.1 Hade den en kompis, så är paret avslutat, ta bort ( ur stacken
4. Är stacken tom fanns det endast par av parenteser

Citera flera Citera

2015-05-25 22:15

RedRetro

Medlem

Plats: Stockholm
Registrerad: Jun 2011

●

Skrivet av Lamposksk:

@Killbom: Ingen aning... :S Fattar inte vad jag håller på med atm ens.

Vill försöka få ut när det är balanserade parenteser så ska de stå att det är balanserat eller ej, och det kan jag fixa lätt med labels, men sen så äre ju allt annat som man inte har en aning om.

Har du förstått dig på hur en stack fungerar och hur du kan använda dig av den för att lösa uppgiften? Om inte bör du först läsa på lite mer, exempelvis på wikipedia.

Men jag illustrerar också med ett exempel: Se en stack som en trave med tallrikar i kön i en skolmatsal. Allt du kan göra är:

a) Titta på den översta tallriken (den brukade alltid vara smutsig ). Detta kallas för "peek".
b) Lägga på en tallrik på högen (push).
c) Ta bort en tallrik från högen (pop).

Nu till din uppgift:
För att parenteserna i en sträng skall vara välbalanserad måste det finnas lika många högerparenteser som vänsterparenteser. Hur kontrollerar man detta genom en stack? Jo, genom att för varje vänsterparentes "(" pusha till stacken, och för varje högerparentes ")" poppa från stacken. För att säkerställa att parenteserna är välbalanserade måste du:

a) Kontrollera att stacken inte är tom om du stöter på en högerparentes (då finns det ju inget att poppa). Detta är ett resultat av att det finns minst en högerparentes mer än vänsterparenteser.

b) När du har gått igenom hela strängen kontrollera att stacken är tom. Om stacken inte är tom vet du att det finns minst en vänsterparentes mer än högerparenteser.

Visa signatur

Citera för svar!

Citera flera Citera (2)

2015-05-25 22:18

Lamposksk

Medlem

Registrerad: Maj 2015

●

@anon81912: Aaah nu så börjar ja fatta, fixade ett par saker. Men det är fortf något fel, fattar inte vad, för att jag kollar om jag har en ) och efter det så peekar jag för att se om ( finns och det funkar inte.. =/

Nya koden:

   Stack<char> Källkod = new Stack<char>();

            string Parentes = tbxParentes.Text;
          
             foreach (char A in Parentes)
            {
                if (Parentes == "(")
                {
                    Källkod.Push(A);                    
                }
                if (Parentes == ")")
                {
                    Källkod.Push(A);
                    
                    if (Källkod.Peek() == '(')
                    {                                             
                        lblUtskrift.Text = "Rätt";                       
                    }
                    else
                    {
                        lblUtskrift.Text = "Fel";
                    }
                }
            }
        }
    }
}

Citera flera Citera

2015-05-25 23:32

Lamposksk

Medlem

Registrerad: Maj 2015

●

@RedRetro: Nya koden:

Stack<char> Källkod = new Stack<char>();

string Parentes = tbxParentes.Text;

foreach (char A in Parentes)
{
if (Parentes == "(")
{
Källkod.Push(A);
}
if (Parentes == ")")
{
Källkod.Push(A);

if (Källkod.Peek() == '(')
{
lblUtskrift.Text = "Rätt";
}
else
{
lblUtskrift.Text = "Fel";
}
}
}
}
}
}

Ser det bättre ut?

Redigerat in [code]-taggar

Citera flera Citera

2015-05-26 00:18

RedRetro

Medlem

Plats: Stockholm
Registrerad: Jun 2011

●

Skrivet av Lamposksk:

@RedRetro: Nya koden:

Stack<char> Källkod = new Stack<char>();

string Parentes = tbxParentes.Text;

foreach (char A in Parentes)
{
if (Parentes == "(")
{
Källkod.Push(A);
}
if (Parentes == ")")
{
Källkod.Push(A);

if (Källkod.Peek() == '(')
{
lblUtskrift.Text = "Rätt";
}
else
{
lblUtskrift.Text = "Fel";
}
}
}
}
}
}

Ser det bättre ut?

Nej, det där ser tyvärr inte rätt ut. Det verkar som att du fortfarande inte förstår den grundläggande lösningsidén som presenterats här i tråden (av bl.a. Killbom och mig).

Du vill:
1) Gå igenom strängen tecken för tecken - Uppfyllt!
2) Om tecknet är en vänsterparentes, pusha den till stacken - Uppfyllt!
3) Om tecknet är en högerparentes OCH om det fortfarande finns element kvar i stacken, poppa det översta elementet i stacken - Inget av detta är uppfyllt!
4) Efter du har gått igenom hela strängen (d.v.s. utanför loopen), kontrollera om det finns några element kvar i stacken - Ej uppfyllt!
5) Om det finns element kvar, printa att parenteserna är obalanserade. Annars, printa att parenteserna är balanserade - Ej uppfyllt!

Visa signatur

Citera för svar!

Citera flera Citera (1)

2015-05-26 00:58

Biberu

Legendarisk ★

Hedersmedlem

Registrerad: Dec 2002

●

@Lamposksk: Om du känner dig osäker på vad du behöver be datorn om så kan det hjälpa att skriva lösningen i pseudokod och arbeta igenom algoritmen manuellt, på det sättet delar du upp problemet i två separata steg och behöver inte bekymra dig om hur det ska se ut i C# direkt. Låtsas att du har en sekreterare som tolkar dig extremt bokstavligt och ge försök ge denne rätt instruktioner på vanlig svenska:

Låt antalet poäng vara 0.

För varje tecken i texten:
    Om tecknet är en öppningsparentes:
        Lägg till ett poäng.
    
    Om tecknet är en stängningsparentes:
       Om du inte har några poäng:
            FEL: Det finns inget att avsluta.
        Annars:
            Ta bort ett poäng.

Om du inte har några poäng kvar:
    OK.
Annars:
    FEL: Du har oavslutade grupper.

Eller med illustrationer:

+----------------------+
| ....(.......)....... |
| ^                    | Börjar här: Stack tom.
|     ^                | Öka din stack med ett.
|             ^        | Din stack är inte tom. Minska med ett och fortsätt.
|                    ^ | Strängen är slut. Stack tom.
|                      |     Allt är OK.
+----------------------+

+----------------------+
| ....(.......)...(... |
| ^                    | Börjar här: Stack tom.
|     ^                | Öka din stack med ett.
|             ^        | Din stack är inte tom. Minska med ett och fortsätt.
|                 ^    | Öka din stack med ett.
|                    ^ | Strängen är slut. Stack inte tom.
|                      |     FEL: Du har en oavslutad grupp.
+----------------------+

+----------------------+
| ....(.......)...)... |
| ^                    | Börjar här: Stack tom.
|     ^                | Öka din stack med ett.
|             ^        | Din stack är inte tom. Minska med ett och fortsätt.
|                 ^    | Din stack är redan tom. Avbryt.
|                      |     FEL: Det fanns inget att avsluta. 
+----------------------+

Senast redigerat 2015-05-26 03:11

Visa signatur

Abstractions all the way down.

Citera flera Citera (3)

2015-05-26 18:07

Lamposksk

Medlem

Registrerad: Maj 2015

●

@RedRetro: Gjorde exakt som du sa (Tror ja?) Och det går ändå inte. =(

  private void btnKontrollera_Click(object sender, EventArgs e)
        {

            Stack<char> Källkod = new Stack<char>();


            string Parentes = tbxParentes.Text;



            foreach (char A in Parentes)
            {
                if (Parentes == "(")
                {
                    Källkod.Push(A);

                }

                if (Parentes == ")")
                {

                    if (Källkod.Count() >= 1)
                    {

                        Källkod.Pop();

                    }
                    else
                    {
                        Källkod.Push(A);
                    }


                    if (Källkod.Count() < 0)
                    {
                        lblUtskrift.Text = "Parenteserna är obalanserade";


                        if (Källkod.Count() > 0)
                        {
                            lblUtskrift.Text = "Parenteserna är balanserade";
                        }
                    }

                }
            }
        }
    }
}

Senast redigerat 2015-05-26 18:56

Citera flera Citera

2015-05-26 18:10

anon81912

Inaktiv

Registrerad: Feb 2006

●

Skrivet av Lamposksk:

@RedRetro: Gjorde exakt som du sa (Tror ja?) Och det går ändå inte. =(

Du gör inte alls som han sa. Kolla vad du har i och utanför loopen. Gå igenom koden rad för rad och jämför med det bibliotek av exempel du fått.

Citera flera Citera

2015-05-26 18:43

http://jsfiddle.net/chmpkykn/

CyberVillain

Avstängd

Plats: Stockholm
Registrerad: Dec 2003

●

Här har du en i javascript du kan ju inte få det för lätt serverat

Visa signatur

Min blogg

Citera flera Citera

2015-05-26 19:01

gaminggirl

Medlem

Plats: Lund
Registrerad: Okt 2011

●

Skrivet av Lamposksk:

@Killbom: Aaah nu så börjar ja fatta, fixade ett par saker. Men det är fortf något fel, fattar inte vad, för att jag kollar om jag har en ) och efter det så peekar jag för att se om ( finns och det funkar inte.. =/

Nya koden:

   Stack<char> Källkod = new Stack<char>();

            string Parentes = tbxParentes.Text;
          
             foreach (char A in Parentes)
            {
                if (Parentes == "(")
                {
                    Källkod.Push(A);                    
                }
                if (Parentes == ")")
                {
                    Källkod.Push(A);
                    
                    if (Källkod.Peek() == '(')
                    {                                             
                        lblUtskrift.Text = "Rätt";                       
                    }
                    else
                    {
                        lblUtskrift.Text = "Fel";
                    }
                }
            }
        }
    }
}

Nej, det stämmer att det inte fungerar. Om du lägger en sluparentes överst i högen innan du tittar vad som är överst i den kommer det alltid vara en slutparentes överst.

Om du hittar en slutparentes ska du inte lägga den på högen, du ska titta vad som är överst i högen. om det inte är en startparentes är det fel och du ska bryta.

Visa signatur

Citera flera Citera

2015-05-26 19:04

Lamposksk

Medlem

Registrerad: Maj 2015

●

@anon81912:

Sådär, nu fick jag det typ till att funka, det enda som inte funka var att när jag bara skriver ) så krashar programmet och när jag skriver t.ex ()( så står det ändå rätt. Men () funkade bra och ( så stog det fel, vilket det ska vara.

private void btnKontrollera_Click(object sender, EventArgs e)
        {

            Stack<char> Källkod = new Stack<char>();


            string Parentes = tbxParentes.Text;



            foreach (char A in Parentes)
            {
                if (Parentes == "(")
                {
                    Källkod.Push(A);

                }

                else if (Parentes == ")")
                {

                    if (Källkod.Last() == '(')
                    {

                        Källkod.Push(A);
                    }
                    else
                    {
                        Källkod.Pop();
                    }
                }
            }

            if (Källkod.Count == 0)
            {
                lblUtskrift.Text = "Rätt";

            }

            else if (Källkod.Count >= 1)
            {
                lblUtskrift.Text = "Fel";
            }
              
        }
    }
}

Citera flera Citera

2015-05-26 19:05

CyberVillain

Avstängd

Plats: Stockholm
Registrerad: Dec 2003

●

Skrivet av gaminggirl:

Nej, det stämmer att det inte fungerar. Om du lägger en sluparentes överst i högen innan du tittar vad som är överst i den kommer det alltid vara en slutparentes överst.

Om du hittar en slutparentes ska du inte lägga den på högen, du ska titta vad som är överst i högen. om det inte är en startparentes är det fel och du ska bryta.

Det är onödigt komplext om du istället bara räknar upp ett för ( och minus ett för ) så slipper du massor med kod, se mitt exempel ovan

Visa signatur

Min blogg

Citera flera Citera

2015-05-26 19:09