Odwrócona notacja polska

0

Witam,
mam za zadanie napisanie kalkulatora odwróconej notacji polskiej z wykorzystaniem własnej implementacji stosu. Mam stos samorozszerzający się, z którego usunąłem zbędne metody. Nie jestem wirtuozem programowania, ale zawsze staram się pisać kod po swojemu bez kopiowania. Coś jest na pewno źle (bo nie działa), ale ciężko jest mi to zlokalizować. Po kilku godzinach prób, rozpisywania na kartce i przeszukiwania internetu dochodzę do wniosku, że może lepiej jest to tu wrzucić. Może jakaś mądra głowa spojrzy i od razu stwierdzi co jest źle, a może po prostu trzeba to napisać od nowa.
Z góry dziękuję za pomoc.

#include <iostream>
#include <sstream>
#include <string>
using namespace std;

struct lista
{
    lista *next;
    double dane;
};

class stack
{
 lista *stos1;
 public:
     stack();
     ~stack();
     void push(double);
     void pop();
     lista *value(); 
};

stack::stack()
{
    stos1=NULL;             //zerowanie wskaznika na pierszy element stosu (head)
}

stack::~stack()
{
    while (stos1)           //dopoki jest cos na glowie to usuwaj
    {
        pop();
    }
}

void stack::push(double v)
{
    lista *e = new lista;   //stworzenie nowej zmiennej typy strukturowego
    e->dane = v;            //przypisanie do zmiennej podanej wartosci
    e->next = stos1;        //przypisanie do wzkaznika szczytu
    stos1 = e;              //nowy szczyt
}

void stack::pop()
{
    if (stos1)
    {
        lista *e = stos1;   //zapamietanie bierzacego szczuty
        stos1 = stos1->next;//zamiana wskaznika
        delete e;           //usuniecie e
    }
}
lista *stack::value()
{
    return stos1;
}
int main()
{
    stack stos1;
    stringstream strumien;
    string ciagZnakow="33+";
    double cyfra_znak;
    double a,b,c;
    int dlugoscCiaguZnakow=ciagZnakow.length()-1;
    for(int i=0; i<=dlugoscCiaguZnakow; i++) //petla odczytujaca kazdy znak ze stringa
    {
        strumien<<ciagZnakow[i];
        if(strumien>>cyfra_znak)        //jezeli to co jest w strumieniu jest typu liczbowego (double) to  na stos
        {
            stos1.push(ciagZnakow[i]);
        }
        else                            // jak nie to:
        {
            a=stos1.value()->dane;      //wartosc ze szczytu do zmiennej a
            stos1.pop();                //zdjecie wartosci ze szczytu
            b=stos1.value()->dane;      //wartosc ze szczytu do zmiennej b
            stos1.pop();                //zdjecie wartosci ze szczytu
            switch(ciagZnakow[i])          //w zaleznosci od tego co jest w zmiennej 'cyfra_znak'
            {
                case '+': c=a+b; break;
                case '-': c=a-b; break;
                case '*': c=a+b; break;
                case '/': c=a+b; break;
            }
            stos1.push(c);              //wynik na stos
        }
    }
    cout<<stos1.value();
    return 0;
}
2
Shimek napisał(a):

Po kilku godzinach prób, rozpisywania na kartce i przeszukiwania internetu dochodzę do wniosku, że może lepiej jest to tu wrzucić. Może jakaś mądra głowa spojrzy i od razu stwierdzi co jest źle, a może po prostu trzeba to napisać od nowa.

Dobra ściema.

#include <iostream>
#include <sstream>
#include <string>
using namespace std;

struct lista
{
    lista *next;
    double dane;
};

class stack
{
 lista *stos1;
 public:
     stack();
     ~stack();
     void push(double);
     void pop();
     lista *value(); 
};

Użyj std::vector. Jak musisz koniecznie zaimplementować listę i stos, to zastanów się nad nie używaniem nagich wskaźników.

        strumien<<ciagZnakow[i];
        if(strumien>>cyfra_znak)        //jezeli to co jest w strumieniu jest typu liczbowego (double) to  na stos

3 poszła do strumien.
3 została wyciągnięta ze strumien. strumien ustawił eofbit (dokumentacja!), kolejny zapis do strumien nie wyzewruje flag, nie da się już wykonać żadnego poprawnego odczytu bez zawołania clear ...

I na koniec, zaprzyjaźnij się z debugerem.

2

Na pewno błąd jest tu:

                case '*': c=a+b; break;
                case '/': c=a+b; break;

Ale może istnieć wiele innych.

#include <iostream>
#include <iomanip>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

double opp(string str)
{
    vector<double> stack;
    istringstream is(str);
    while(is)
    {
        double value;
        if(is>>value) stack.push_back(value);
        else
        {
            is.clear(ios::goodbit);
            string ch;
            is>>ws>>ch;
            double b=stack.back();
            stack.pop_back();
            double a=stack.back();
            stack.pop_back();
            if(ch=="add") stack.push_back(a+b);
            else if(ch=="sub") stack.push_back(a-b);
            else if(ch=="mul") stack.push_back(a*b);
            else if(ch=="div") stack.push_back(a/b);
            else if(ch!="") cout<<"Bad operation: "<<ch<<endl;
            else break;
        }
    }
    return stack.front();
}

int main()
{
    cout<<opp("3 3 add 7 mul");
    return 0;
}
3

Powyżej Masz rozwiązanie, ale akurat, dydaktyka, nie jest mocną stroną @_13th_Dragon :). Jak Piszesz stos "samorozszerzający się", czyli po polsku stos dynamiczny, to lepiej na bazie std::vector, a nie linked listy.
Metody stosu:

  • push;
  • pop;
  • isEmpty.

Te muszą być, co tam robi robi lista *value();, to jest złamanie istoty ADT .
Co do samego algorytmu, nie case, Zrób funkcje: add, divide, etc... Wejściowego stringa lepiej "stokenizować", czyli: 33+ -> ["3", "3", "+"], (wektor stringów) będzie łatwiej, Zrobisz to:
if(strumien>>cyfra_znak),
po ludzku, bo jest jakieś dziwadło.

https://www.fluentcpp.com/201[...]1/how-to-split-a-string-in-c/

0

Totalna parodia.

  1. Notacja postfiksowa została wymyślona, aby wyliczać normalne wyrażenia, czyli infiksowe, np.:
    1 + 23^2 + 2sin(3pi/4)
    przekształcamy na:
    1 2 3 2 ^
    + 2 3 pi 2 / sin *

  2. i to jest już gotowy wynik, który wyliczamy łatwo - z użyciem stosu!

o tak:
push(1)
push(2)
push(3)
push(2)

teraz mamy operację: ^
zatem zdejmujemy argumenty i wykonujemy:
push(pop ^ pop)
itd.

Tworzenie 'stosu' z gotowego wyrażenia w postfiksie jest bezcelowe - to się po prostu oblicza za pomocą stosu!

2
bonifacy napisał(a):

Tworzenie 'stosu' z gotowego wyrażenia w postfiksie jest bezcelowe - to się po prostu oblicza za pomocą stosu!

Nie zupełnie, jest to całkiem dobre zadanie dydaktyczne na tworzenie własnego stosu i posługiwanie się nim.

0

Pewnie że można zrobić sobie stos z wyrażeniami w tej odwrotnej notacji,
ale to ma sens jedynie w przypadku, gdy te obliczenia będą wykonywane wielokrotnie, tz. w przypadku gdy w wyrażeniu występują zmienne.

Przykład - chcemy narysować wykres funkcji, którą wprowadza użytkownik, np.:
z = 2cos(sqrt(1 - x^2-y^2)) + 5y;

wtedy przerabiamy to na wygodne - proste do obliczania wyrażenie, czyli notacja postfiksowa;
no i wyliczamy to np. 10000 razy, bo po siatce: x = 0..1 i y = ... z krokiem 0.01;

Tyle że teraz na stosie mamy symbole - obiekty reprezentujące liczby i operatory, a nie proste liczby.

push symbol number 32.6
push symbol = variable x
push symbol function sin, 1 arg
push function add, 2 args
push vector, 4 dim
...

1
bonifacy napisał(a):

Pewnie że można zrobić sobie stos z wyrażeniami w tej odwrotnej notacji,
ale to ma sens jedynie w przypadku, gdy te obliczenia będą wykonywane wielokrotnie, tz. w przypadku gdy w wyrażeniu występują zmienne.

A możesz podać chociażby jeden sensowny a zarazem nie czysto dydaktyczny przypadek, w którym zmienne nie są potrzebne?

0

standardowe kalkulatory nie pozwalają na używanie zmiennych.

(3 + 4.5)*5 - 3 = ... ok.

natomiast:
sin(x) = ?
i już żaden kalkulator tego nie ogarnie, i nawet nie pozwoli tego wpisać - bo on nie zna pojęcia 'zmiennej'.

obiekt typu liczba = zmienna lub stała.

Przykład, jak wygląda wyliczanie takiego wyrażenia - na symbolach:

double calcPost(const Symbol *s)
{
   double stack[32], *st = stack;

   for(; s->action != C_NIC; s++)
     {
       if( s->action == C_NUM || s->action == C_LVAL ) *st++ = *s; // push: zmienna lub stała
       else // operatory
        {
          int a = ( s->isRL() ) ? 2 : s->nArgs();  // potrzebujemy liczbę argumentów

          if( a == 1 ) st[-1] = s->f1(st[-1]);
          else //if( n == 2 ) 
            {
              st--; // pop
              st[-1] = s->f2(st[-1], st[0]); // obliczenie + pop i push wynik operacji...
            }
        }
     }

   return stack[0]; // finalny wynik zawsze jest na wierzchołku
}
2
bonifacy napisał(a):

Totalna parodia.
(...)
Tworzenie 'stosu' z gotowego wyrażenia w postfiksie jest bezcelowe - to się po prostu oblicza za pomocą stosu!

Pytanie dotyczy konkretnego problemu, który zaprezentował op, a nie zastosowania ONP. Nie wiem, co w tym niezrozumiałego.
Wyodrębnienie podproblemu z szerszego zagadnienia ma swoje plusy w dydaktyce. W tym wypadku zrozumienie języka programowania, typowych konstrukcji programistycznych czy przykładowo istoty tokenizacji w parsowania. Op jest ewidentnie na początku drogi z programowaniem i ma w aktualnym momencie problemy natury implementacyjnej. Mam więc wątpliwości czy ironiczny ton i "o tak, push, push, pop i masz kalkulator gotowy" jest pomocne.

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0