Stapels en wachtrijen # 2

Een algebraïsche uitdrukking is een legale combinatie van operatoren en operanden. Operand is de hoeveelheid waarop een wiskundige bewerking wordt uitgevoerd. Operand kan een variabele zijn zoals x, y, z of een constante zoals 5, 4, 6 etc. Operator is een symbool dat een wiskundige of logische bewerking tussen de operanden aangeeft. Voorbeelden van bekende operatoren zijn onder meer +, -, *, /, ^ enz. Een algebraïsche uitdrukking kan worden weergegeven met drie verschillende notaties. Het zijn tussenvoegsels, postfixen en voorvoegselnotaties:

Tussenvoegsel : het is de fo r m van een rekenkundige uitdrukking waarin we de rekenkundige operator tussen de twee fixeren (plaatsen) operanden. Voorbeeld: (A + B) * (C – D)

Voorvoegsel : het is de vorm van een rekenkundige notatie waarin we de rekenkundige operator fixeren (plaatsen) vóór (pre) zijn twee operanden. De voorvoegselnotatie wordt de Poolse notatie genoemd (vanwege de Poolse wiskundige Jan Lukasiewicz in het jaar 1920). Voorbeeld: * + A B – C D

Postfix : het is de vorm van een rekenkundige uitdrukking waarin we de rekenkundige operator repareren (plaatsen) na (post) zijn twee operanden. De postfix-notatie wordt achtervoegselnotatie genoemd en wordt ook wel de omgekeerde Poolse notatie genoemd. Voorbeeld: A B + C D – *

De drie belangrijke kenmerken van postfix-expressie zijn:

1. De operanden behouden dezelfde volgorde als in de equivalente tussenvoegseluitdrukking.

2. De haakjes zijn niet nodig om de uitdrukking ondubbelzinnig aan te duiden.

3. Bij het evalueren van de postfix-expressie is de prioriteit van de operatoren niet langer relevant. We beschouwen vijf binaire bewerkingen: +, -, *, / en $ of ↑ (machtsverheffen). Voor deze binaire bewerkingen, het volgende in de volgorde van prioriteit (van hoog naar laag):

Toepassingen van stacks:

1. Stack wordt gebruikt door compilers om te controleren op het balanceren van haakjes, haakjes en accolades.

2. Stack wordt gebruikt om een ​​postfix-uitdrukking te evalueren.

3. Stack wordt gebruikt om een ​​tussenvoegseluitdrukking om te zetten in een postfix / voorvoegselvorm.

4. Bij recursie worden alle tussenliggende argumenten en retourwaarden opgeslagen op de stapel van de processor.

5. Tijdens een functieaanroep worden het retouradres en de argumenten op een stapel geduwd en bij terugkeer worden ze eraf gepopt. Conversie van tussenvoegsel naar postfix:

Conversie van tussenvoegsel naar postfix-expressie

De procedure voor het converteren van een tussenvoegsel-expressie naar een postfix-expressie is als volgt: (algoritme)

1. Scan de tussenvoegseluitdrukking van links naar rechts.

2.

a) Als het gescande symbool links tussen haakjes staat, duw het dan op de stapel.

b) Als het gescande symbool een operand is, plaats het dan direct in de postfix-expressie (output).

c) Als het gescande symbool een rechter haakje is, blijf dan alle items uit de stapel halen en plaats ze in de postfix-uitdrukking totdat we het overeenkomende linkerhaakje krijgen.

d) Als het gescande symbool een operator is, ga dan verder met het verwijderen van alle operatoren van de stapel en plaats ze in de postfix-uitdrukking, als en slechts als de prioriteit van de operator bovenaan de stapel groter is dan (of groter dan of gelijk) aan de voorrang van de gescande operator en duw de gescande operator op de stapel, anders duw de gescande operator op de stapel

Evaluatie van postfix-expressie

1. Scan de postfix-uitdrukking van links naar rechts.

2. Als het gescande symbool een operand is, plaats het dan op de stapel.

3. Als het gescande symbool een operator is, knalt u twee symbolen uit de stapel en wijst u deze toe aan respectievelijk operand 2 en operand1. Voer een bewerking uit en druk op stapel

4. Herhaal stap 2 en 3 tot het einde van de uitdrukking.

Recursie

Recursie is bedrieglijk eenvoudig in bewering, maar uitzonderlijk gecompliceerd in implementatie. Recursieve procedures werken prima bij veel problemen. Veel programmeurs geven de voorkeur aan recursie, hoewel er eenvoudiger alternatieven beschikbaar zijn. Het is omdat recursie elegant is om te gebruiken, hoewel het kostbaar is in termen van tijd en ruimte.

Inleiding tot recursie:

Een functie is recursief als een instructie in de body van de functie zichzelf aanroept. Recursie is het proces waarbij iets op zichzelf wordt gedefinieerd. Om een ​​computertaal recursief te laten zijn, moet een functie zichzelf kunnen aanroepen. Laten we bijvoorbeeld eens kijken naar de functie factr () die hieronder wordt weergegeven, die de faculteit van een geheel getal computers.

Een niet-recursieve of iteratieve versie voor het vinden van de faculteit is als volgt:

De werking van de niet-recursieve versie is duidelijk, aangezien deze een lus gebruikt die begint bij 1 en eindigt bij de doelwaarde, en elk getal progressief vermenigvuldigt met het bewegende product. Wanneer een functie zichzelf aanroept, krijgen nieuwe lokale variabelen en parameters opslag toegewezen op de stapel en wordt de functiecode vanaf het begin uitgevoerd met deze nieuwe variabelen. Een recursieve aanroep maakt geen nieuwe kopie van de functie. Alleen de argumenten en variabelen zijn nieuw. Als elke recursieve aanroep terugkeert, worden de oude lokale variabelen en parameters verwijderd uit de stapel en wordt de uitvoering hervat op het punt van de functieaanroep binnen de functie.

Bij het schrijven van recursieve functies moet er ergens een exit-voorwaarde zijn om de functie te dwingen terug te keren zonder dat de recursieve aanroep wordt uitgevoerd. Als er geen exitconditie is, zal de recursieve functie voor altijd doorlopen totdat je geen stack meer hebt en een fout aangeven over gebrek aan geheugen of stack overflow.

Verschillen tussen recursie en iteratie:

* Beide hebben te maken met herhaling.

* Beide hebben betrekking op een beëindigingstest.

* Beide kunnen oneindig voorkomen.

Iteratie gebruikt expliciet een herhalingsstructuur.

Met recursie wordt herhaling bereikt door herhaalde functieaanroepen.

De iteratie wordt beëindigd wanneer de lus eindigt

Recursie stopt wanneer een basisscenario wordt herkend

Iteratie blijft de teller aanpassen totdat de continuatieconditie van de lus mislukt.

Recursie blijft eenvoudige versies van het oorspronkelijke probleem produceren totdat het basisscenario is bereikt

Iteratie vindt normaal gesproken plaats binnen een lus, dus het extra geheugengebruik wordt vermeden

Recursie veroorzaakt een andere kopie van de functie en daardoor een aanzienlijke bezetting van geheugenruimte.

Het vermindert de werktijd van de processor

Het verhoogt de tijd van de processor

Factorieel van een bepaald getal:

De werking van de recursieve factoriële functie is als volgt:

Begin met een natuurlijk getal N (in ons voorbeeld 5).

De recursieve definitie is:

n = 0, 0! = 1 – Basiskoffer

n & gt; 0, n! = n * (n – 1)! – Recursief geval

Recursiefactorials:

5! = 5 * 4! = 5 * 4 * 3! = 5 * 4 * 3 * 2! = 5 * 4 * 3 * 2 * 1! = 5 * 4 * 3 * 2 * 1 * 0! = 5 * 4 * 3 * 2 * 1 * 1 = 120

We definiëren 0! gelijk aan 1, en we definiëren faculteit N (waarbij N & gt; 0), als N * faculteit (N-1). Alle recursieve functies moeten een uitgangsvoorwaarde hebben die een toestand is wanneer de functie wordt beëindigd. De uitgangsvoorwaarde in dit voorbeeld is wanneer N = 0.

Traceren van de stroom van de factorial () functie:

Wanneer de faculteitfunctie voor het eerst wordt aangeroepen met bijvoorbeeld N = 5, gebeurt het volgende:

FUNCTIE: Is N = 0? Geen functie retourwaarde = 5 * faculteit (4) Op dit moment wordt de functie faculteit opnieuw aangeroepen, met N = 4.

FUNCTIE: Is N = 0? No Function Return Value = 4 * faculteit (3) Op dit moment wordt de functie faculteit opnieuw aangeroepen, met N = 3.

FUNCTIE: Is N = 0? No Function Return Value = 3 * faculteit (2) Op dit moment wordt de functie faculteit opnieuw aangeroepen, met N = 2.

FUNCTIE: Is N = 0? No Function Return Value = 2 * faculteit (1) Op dit moment wordt de functie faculteit opnieuw aangeroepen, met N = 1.

FUNCTIE: Is N = 0? No Function Return Value = 1 * faculteit (0) Op dit moment wordt de functie faculteit opnieuw aangeroepen, met N = 0.

FUNCTIE: Is N = 0? Ja Functie retourwaarde = 1

Teken nu de weg terug naar boven! Kijk, de faculteitfunctie werd zes keer aangeroepen. Bij elke aanroep op functieniveau bestaan ​​alle bovenstaande aanroepen op functieniveau nog steeds! Dus als we N = 2 hebben, wachten de functie-instanties waarin N = 3, 4 en 5 nog steeds op hun retourwaarden.

Dus de functieaanroep waarbij N = 1 als eerste wordt getraceerd, zodra de laatste oproep 0 retourneert. Dus de functieaanroep waarbij N = 1 1 * 1 retourneert, of 1. De volgende hogere functieaanroep, waarbij N = 2 , retourneert 2 * 1 (1, want dat is wat de functieaanroep is waarbij N = 1 geretourneerd). Blijf gewoon doorwerken tot de definitieve oplossing is verkregen.

Wanneer N = 2, 2 * 1 of 2 werd geretourneerd. Wanneer N = 3, 3 * 2 of 6 werd geretourneerd. Wanneer N = 4, 4 * 6 of 24 werd geretourneerd. Wanneer N = 5, 5 * 24 of 120 werd geretourneerd. En aangezien N = 5 de eerste functieaanroep was (en dus de laatste die werd opgeroepen), wordt de waarde 120 geretourneerd.

Oorspronkelijk gepubliceerd op http://computerscienceinanutshell.wordpress.com op 2 november 2020.