Sto leggendo il Algorithm Design Manual Seconda edizione e questo è da una domanda di esercizio. Citando la questioneLa stringa di controllo ha parentesi bilanciata
Un problema comune per i compilatori e editor di testo è determinare se le parentesi in una stringa sono equilibrata e correttamente annidati. Per esempio , la stringa ((())())() contiene coppie nidificate correttamente di parentesi , che le stringhe)() ( e()) no. Fornire un algoritmo che restituisce true se una stringa contiene parentesi nidificate e bilanciate correttamente e false se in caso contrario. Per il credito completo, identificare la posizione della prima parentesi incriminata se la stringa non è correttamente nidificata e bilanciata.
La domanda è nella categoria pile, code e elenchi. Ecco cosa ho scritto in C#.
const char LeftParenthesis = '(';
const char RightParenthesis = ')';
bool AreParenthesesBalanced(string str, out int errorAt)
{
var items = new Stack<int>(str.Length);
errorAt = -1;
for (int i = 0; i < str.Length; i++)
{
char c = str[i];
if (c == LeftParenthesis)
items.Push(i);
else if (c == RightParenthesis)
{
if (items.Count == 0)
{
errorAt = i + 1;
return false;
}
items.Pop();
}
}
if (items.Count > 0)
{
errorAt = items.Peek() + 1;
return false;
}
return true;
}
Questo funziona bene. Ma non sono sicuro che questo sia il metodo giusto per affrontare questo problema. Qualche idea migliore è la benvenuta.
potrebbe verificare http://refactormycode.com/, che è più orientato verso questo genere di cose. – Larsenal
Sì, questo è il modo giusto ed è anche usato per analizzare l'espressione matematica. – TheVillageIdiot