Przeczytaj

Polecenie 1

Przeanalizuj prezentację, która rozszerza program omówiony w filmie, umożliwiając użytkownikowi wprowadzanie operandówoperandoperandów składających się z wielu cyfr.

Specyfikacja problemu:

Dane:

wyrazenie – łańcuch znaków, pobrane od użytkownika wyrażenie zapisane w klasycznej notacjinotacja klasyczna (notacja infiksowa)klasycznej notacji, które ma zostać przekształcone na swój odpowiednik w ONP

Wynik:

wyrażenie arytmetyczne zamienione na ONPONP

RgpTYIWermCZi1

Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Polecenie 2

Zmodyfikuj program przedstawiony w prezentacji tak, by przekształcał wyrażenie arytmetyczne zapisane w notacji postfiksowej na postać infiksową.

Uruchom swój program w środowisku lokalnym i przetestuj dla następującego wyrażenia arytmetycznego zapisanego w postaci postfiksowej:

8 9 * 3 6 + *

Zastosuj pełne nawiasowanie.

Poprawny wynik dla powyższych danych:

((8*9)*(3+6))

Linia 1. prawy ukośnik prawy ukośnik Poniżej znajdziesz program z sekcji Przeczytaj przecinek który należy zmodyfikować kropka. Linia 3. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 4. kratka include otwórz nawias ostrokątny list zamknij nawias ostrokątny. Linia 6. using namespace std średnik. Linia 8. int pobierzPriorytet otwórz nawias okrągły string op zamknij nawias okrągły otwórz nawias klamrowy. Linia 9. if otwórz nawias okrągły op znak równości znak równości cudzysłów plus cudzysłów kreska pionowa kreska pionowa op znak równości znak równości cudzysłów minus cudzysłów zamknij nawias okrągły otwórz nawias klamrowy. Linia 10. return 1 średnik. Linia 11. zamknij nawias klamrowy. Linia 12. else if otwórz nawias okrągły op znak równości znak równości cudzysłów asterysk cudzysłów kreska pionowa kreska pionowa op znak równości znak równości cudzysłów prawy ukośnik cudzysłów zamknij nawias okrągły otwórz nawias klamrowy. Linia 13. return 2 średnik. Linia 14. zamknij nawias klamrowy. Linia 15. else if otwórz nawias okrągły op znak równości znak równości cudzysłów kareta cudzysłów zamknij nawias okrągły otwórz nawias klamrowy. Linia 16. return 3 średnik. Linia 17. zamknij nawias klamrowy. Linia 18. else otwórz nawias klamrowy. Linia 19. return 0 średnik. Linia 20. zamknij nawias klamrowy. Linia 21. zamknij nawias klamrowy. Linia 23. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 24. list otwórz nawias ostrokątny string zamknij nawias ostrokątny stos średnik. Linia 26. string wyrazenie średnik. Linia 27. getline otwórz nawias okrągły cin przecinek wyrazenie zamknij nawias okrągły średnik. Linia 29. list otwórz nawias ostrokątny string zamknij nawias ostrokątny elementyWyrazenia średnik. Linia 31. int pozycjaSpacji znak równości 0 średnik. Linia 33. while otwórz nawias okrągły otwórz nawias okrągły pozycjaSpacji znak równości wyrazenie kropka find otwórz nawias okrągły cudzysłów cudzysłów zamknij nawias okrągły zamknij nawias okrągły wykrzyknik znak równości string dwukropek dwukropek npos zamknij nawias okrągły otwórz nawias klamrowy. Linia 34. elementyWyrazenia kropka push podkreślnik back otwórz nawias okrągły wyrazenie kropka substr otwórz nawias okrągły 0 przecinek pozycjaSpacji zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 35. wyrazenie kropka erase otwórz nawias okrągły 0 przecinek pozycjaSpacji plus 1 zamknij nawias okrągły średnik. Linia 36. zamknij nawias klamrowy. Linia 37. elementyWyrazenia kropka push podkreślnik back otwórz nawias okrągły wyrazenie kropka substr otwórz nawias okrągły 0 przecinek string dwukropek dwukropek npos zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 39. while otwórz nawias okrągły wykrzyknik elementyWyrazenia kropka empty otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 40. string elementWyrazenia znak równości elementyWyrazenia kropka front otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 41. elementyWyrazenia kropka pop podkreślnik front otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 43. if otwórz nawias okrągły elementWyrazenia znak równości znak równości cudzysłów znak równości cudzysłów zamknij nawias okrągły otwórz nawias klamrowy. Linia 45. while otwórz nawias okrągły wykrzyknik stos kropka empty otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 46. string op znak równości stos kropka back otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 47. cout otwórz nawias ostrokątny otwórz nawias ostrokątny op otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów cudzysłów średnik. Linia 48. stos kropka pop podkreślnik back otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 49. zamknij nawias klamrowy. Linia 50. zamknij nawias klamrowy. Linia 51. else if otwórz nawias okrągły elementWyrazenia znak równości znak równości cudzysłów plus cudzysłów kreska pionowa kreska pionowa elementWyrazenia znak równości znak równości cudzysłów minus cudzysłów. Linia 52. kreska pionowa kreska pionowa elementWyrazenia znak równości znak równości cudzysłów asterysk cudzysłów kreska pionowa kreska pionowa elementWyrazenia znak równości znak równości cudzysłów prawy ukośnik cudzysłów. Linia 53. kreska pionowa kreska pionowa elementWyrazenia znak równości znak równości cudzysłów kareta cudzysłów zamknij nawias okrągły otwórz nawias klamrowy. Linia 55. while otwórz nawias okrągły wykrzyknik stos kropka empty otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 56. if otwórz nawias okrągły pobierzPriorytet otwórz nawias okrągły elementWyrazenia zamknij nawias okrągły zamknij nawias ostrokątny pobierzPriorytet otwórz nawias okrągły stos kropka back otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 57. break średnik. Linia 58. zamknij nawias klamrowy. Linia 59. cout otwórz nawias ostrokątny otwórz nawias ostrokątny stos kropka back otwórz nawias okrągły zamknij nawias okrągły otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów cudzysłów średnik. Linia 60. stos kropka pop podkreślnik back otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 61. zamknij nawias klamrowy. Linia 62. stos kropka push podkreślnik back otwórz nawias okrągły elementWyrazenia zamknij nawias okrągły średnik. Linia 63. zamknij nawias klamrowy. Linia 64. else if otwórz nawias okrągły elementWyrazenia znak równości znak równości cudzysłów otwórz nawias okrągły cudzysłów zamknij nawias okrągły otwórz nawias klamrowy. Linia 65. stos kropka push podkreślnik back otwórz nawias okrągły cudzysłów otwórz nawias okrągły cudzysłów zamknij nawias okrągły średnik. Linia 66. zamknij nawias klamrowy. Linia 67. else if otwórz nawias okrągły elementWyrazenia znak równości znak równości cudzysłów zamknij nawias okrągły cudzysłów zamknij nawias okrągły otwórz nawias klamrowy. Linia 68. while otwórz nawias okrągły stos kropka back otwórz nawias okrągły zamknij nawias okrągły wykrzyknik znak równości cudzysłów otwórz nawias okrągły cudzysłów zamknij nawias okrągły otwórz nawias klamrowy. Linia 69. cout otwórz nawias ostrokątny otwórz nawias ostrokątny stos kropka back otwórz nawias okrągły zamknij nawias okrągły otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów cudzysłów średnik. Linia 70. stos kropka pop podkreślnik back otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 71. zamknij nawias klamrowy. Linia 72. stos kropka pop podkreślnik back otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 73. zamknij nawias klamrowy. Linia 74. else otwórz nawias klamrowy. Linia 75. cout otwórz nawias ostrokątny otwórz nawias ostrokątny elementWyrazenia otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów cudzysłów średnik. Linia 76. zamknij nawias klamrowy. Linia 77. zamknij nawias klamrowy. Linia 79. return 1 średnik. Linia 80. zamknij nawias klamrowy.

// Poniżej znajdziesz program z sekcji Przeczytaj, który należy zmodyfikować.

#include <iostream>
#include <list>

using namespace std;

int pobierzPriorytet(string op){
    if(op == "+" || op == "-"){
        return 1;
    }
    else if(op == "*" || op == "/"){
        return 2;
    }
    else if(op == "^"){
        return 3;
    }
    else{
        return 0;
    }
}

int main(){
    list<string> stos;

    string wyrazenie;
    getline(cin, wyrazenie);

    list<string> elementyWyrazenia;

    int pozycjaSpacji = 0;

    while((pozycjaSpacji = wyrazenie.find(" ")) != string::npos){
        elementyWyrazenia.push_back(wyrazenie.substr(0, pozycjaSpacji));
        wyrazenie.erase(0, pozycjaSpacji + 1);
    }
    elementyWyrazenia.push_back(wyrazenie.substr(0, string::npos));

    while(!elementyWyrazenia.empty()){
        string elementWyrazenia = elementyWyrazenia.front();
        elementyWyrazenia.pop_front();

        if(elementWyrazenia == "="){

            while(!stos.empty()){
                string op = stos.back();
                cout << op << " ";
                stos.pop_back();
            }
        }
        else if(elementWyrazenia == "+" || elementWyrazenia == "-"
                || elementWyrazenia == "*" || elementWyrazenia == "/"
                || elementWyrazenia == "^"){

            while(!stos.empty()){
                if(pobierzPriorytet(elementWyrazenia) > pobierzPriorytet(stos.back())){
                    break;
                }
                cout << stos.back() << " ";
                stos.pop_back();
            }
            stos.push_back(elementWyrazenia);
        }
        else if(elementWyrazenia == "("){
            stos.push_back("(");
        }
        else if(elementWyrazenia == ")"){
            while(stos.back() != "("){
                cout << stos.back() << " ";
                stos.pop_back();
            }
            stos.pop_back();
        }
        else{
            cout << elementWyrazenia << " ";
        }
    }

    return 1;
}

R1B1SdE0NWY3t1

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 2. kratka include otwórz nawias ostrokątny stack zamknij nawias ostrokątny. Linia 3. kratka include otwórz nawias ostrokątny string zamknij nawias ostrokątny. Linia 5. using namespace std średnik. Linia 7. string infiksowa otwórz nawias okrągły string ONP zamknij nawias okrągły otwórz nawias klamrowy. Linia 8. stack otwórz nawias ostrokątny string zamknij nawias ostrokątny stos średnik. Linia 9. string wyrazenie średnik. Linia 11. for otwórz nawias okrągły char znak dwukropek ONP zamknij nawias okrągły otwórz nawias klamrowy. Linia 12. if otwórz nawias okrągły isdigit otwórz nawias okrągły znak zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 13. stos kropka push otwórz nawias okrągły string otwórz nawias okrągły 1 przecinek znak zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 14. zamknij nawias klamrowy else if otwórz nawias okrągły znak wykrzyknik znak równości apostrof apostrof zamknij nawias okrągły otwórz nawias klamrowy. Linia 15. string prawy znak równości stos kropka top otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 16. stos kropka pop otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 17. string lewy znak równości stos kropka top otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 18. stos kropka pop otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 19. wyrazenie znak równości cudzysłów otwórz nawias okrągły cudzysłów plus lewy plus znak plus prawy plus cudzysłów zamknij nawias okrągły cudzysłów średnik. Linia 20. stos kropka push otwórz nawias okrągły wyrazenie zamknij nawias okrągły średnik. Linia 21. zamknij nawias klamrowy. Linia 22. zamknij nawias klamrowy. Linia 24. return stos kropka top otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 25. zamknij nawias klamrowy. Linia 27. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 28. string ONP znak równości cudzysłów 8 9 asterysk 3 6 plus asterysk cudzysłów średnik. Linia 29. cout otwórz nawias ostrokątny otwórz nawias ostrokątny infiksowa otwórz nawias okrągły ONP zamknij nawias okrągły otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 30. return 0 średnik. Linia 31. zamknij nawias klamrowy.

#include <iostream>
#include <stack>
#include <string>

using namespace std;

string infiksowa(string ONP) {
    stack<string> stos;
    string wyrazenie;

    for (char znak : ONP) {
        if (isdigit(znak)) {
            stos.push(string(1, znak));
        } else if (znak != ' ') {
            string prawy = stos.top();
            stos.pop();
            string lewy = stos.top();
            stos.pop();
            wyrazenie = "(" + lewy + znak + prawy + ")";
            stos.push(wyrazenie);
        }
    }

    return stos.top();
}

int main() {
    string ONP = "8 9 * 3 6 + *";
    cout << infiksowa(ONP) << endl;
    return 0;
}

Słownik

notacja klasyczna (notacja infiksowa)

sposób zapisu dwuargumentowego wyrażenia arytmetycznego, w którym operator działania zostaje zapisany między operandami, np. 2 + 2

notacja polska (notacja prefiksowa)

sposób zapisu wyrażenia arytmetycznego, w którym operator umieszczony jest przed operandami, np. + 2 2

odwrotna notacja polska (ONP, notacja postfiksowa)

sposób zapisu wyrażenia arytmetycznego, w którym operator umieszczony jest za operandami, np. 2 2 +

operand

liczba, na której wykonywane jest działanie

Przykład 1

Dla wyrażenia arytmetycznego:

27 * 5

liczby 27 oraz 5 to operandy, a znak mnożenia jest operatorem

pełne nawiasowanie

szczególne ustawienie nawiasów w wyrażeniu arytmetycznym w notacji infiksowej; dzięki niemu każde działanie ma jednoznacznie określone dwa operandy za pomocą ujęcia w nawiasy, a także całe działanie jest objęte nawiasem, np. (a+(b⋅c))

Film samouczek

Sprawdź się

Słownik