Pila de estructura de datos de Python y búsqueda en profundidad (pila)

La pila es la estructura auxiliar más utilizada en algoritmos y programas, y sus aplicaciones son muy amplias. La pila se utiliza básicamente de dos maneras:

La división de enteros mantiene sólo la parte entera.

Algoritmo Depth First Search (Depth First Search): la abreviatura en inglés es DFS. Es un algoritmo para recorrer o buscar un árbol o gráfico. Este algoritmo atraviesa los nodos del árbol a lo largo de la profundidad del árbol y busca las ramas del árbol lo más profundo posible. Cuando se hayan explorado todos los bordes del nodo v, la búsqueda retrocederá hasta el nodo inicial del borde donde se encontró el nodo v. Este proceso continúa hasta que se hayan descubierto todos los nodos accesibles desde el nodo de origen. Si todavía hay nodos sin descubrir, seleccione uno de ellos como nodo de origen y repita el proceso anterior. Todo el proceso se repite hasta que se visiten todos los nodos.

Durante el proceso de recorrido en profundidad primero, necesitamos almacenar temporalmente los nodos adyacentes del nodo v actualmente atravesado para que podamos continuar accediendo a ellos cuando regresemos. El orden de los nodos atravesados ​​se ajusta a las características de "último en entrar, primero en salir", por lo que la búsqueda en profundidad se puede implementar mediante "recursión" o "pila".

Dada una referencia a un nodo en un gráfico conectado no dirigido, devuelva una copia profunda (clon) del gráfico.

Cada nodo del gráfico contiene su valor val (int) y una lista de sus vecinos (lista[Nodo]).

Entrada: (((())

Salida: Falso

Solicitar juicio {{{{[[[((()))]]] } }}}

Expresión infija A + B; A + B * C; (A + B) * C

Expresión prefija + AB + A * BC;

Expresión postfija AB +; A B C * +; AB + C*

Los corchetes que deben estar presentes en expresiones infijas desaparecen en expresiones prefijas y postfijas

Ideas

1 Convierta la expresión infija en forma de corchetes completos

2 Mueva todos los operadores al corchete izquierdo donde se encuentra la subexpresión (prefijo) o al corchete derecho (sufijo), luego elimine todos los demás corchetes