Rekurencja i naturalny stos.

Witam, mam do zrobienia zadanie, za które nie wiem jak się zabrać.

Napisz program, wczytujący po jednym wierszu ze standardowego wejścia, oraz wypisujący każdy z tych wierszy w odwrócony sposób (poprzez zmianę kolejności liter - z wyjątkiem znaku nowej linii). Wykorzystaj funkcję rekurencyjną (oraz naturalny stos) do wczytania oraz wypisywania liter (nie wolno zapamiętywać liter w tablicy).

Wejście:
Przykładowy tekst.

Wyjście:
.tsket ywodałkyzrP

Proszę o jakieś wskazówki, bo nie wiem jak można coś wczytać a później wypisać bez zapisania do jakiejś zmiennej.

Nie możesz użyć tablicy, a nie zmiennych. Chyba są jakieś niestandardowe funkcje w C++, które od razu zwracają klepnięty znak. Wtedy możesz zrobić algorytm typu:

procedura R:

1. wczytaj znak i zapamiętaj na stosie
2. jeżeli to nie enter to wywołaj siebie (czyli procedurę R)
3. wypisz zapamiętany znak i wróć

To banalnie proste: pobierasz znak i zapamiętujesz w zmiennej, jeżeli jest on różny od znaku nowej linii to pobierasz ponownie i zapamiętujesz - wykonujesz kolejne zejście rekurencyjne. Na koniec wypisujesz znak. Streszczając - rekurencja z napotkaniem '\n' jako warunkiem stopu i wypisaniem znaku na wyjściu.

void odwracaj(bool pierwsza){
  char literka;
  scanf("%c",&literka);
  if(literka=='\n')
    return;
  else
  {
    odwracaj(false);
    printf("%c",literka);
    if(pierwsza)
        printf("\n");
  }
}

Wywoływane jako odwracaj(true) (ten bool jest po to żeby wiedzieć kiedy wypisać znak nowej linii)

edit: widzę że nie mnie jednego dopadło otwieranie wielu kart na raz ;]

Skoro już w temacie jesteśmy a Wibowit się tutaj pałęta... Uroczy, ryjący psychikę, przykład realizacji w 'trochę' innym języku (Haskell), rekurencja ogonowa z wykorzystaniem pattern matchingu, akcji, kontynuacji i funkcji wzajemnie rekurencyjnych:

module Main where

import Monad 

printReversedStdinLn = loop $ putChar '\n'
    where
      loop cont      = step cont =<< getChar
      step cont '\n' = cont
      step cont char = loop $ putChar char >> cont

main = printReversedLine

Hm, chociaż ten kod chyba nie spełnia założeń zadania... nie korzysta ze stosu w ogóle, wszystko rozbija się o closures na stercie.

Przyjdzie Wibowit to może w Scali napisze.

Z użyciem naturalnego stosu, pod MASM ;)

.686
.mmx
.model flat,stdcall

include \masm32\include\windows.inc
include \masm32\include\kernel32.inc
include \masm32\include\user32.inc

includelib \masm32\lib\kernel32.lib
includelib \masm32\lib\user32.lib

extern __ImageBase:near

.data?
        hConsoleOut     dd ?
        hConsoleIn      dd ?

        szText          db 512 dup(?)
.code

start:

; pobierz uchwyty out/in
        push    STD_OUTPUT_HANDLE
        call    GetStdHandle
        mov     hConsoleOut,eax

        push    STD_INPUT_HANDLE
        call    GetStdHandle
        mov     hConsoleIn,eax

        push    1
        push    offset _ctrlc_handler
        call    SetConsoleCtrlHandler

        mov     esi,offset szText

_read_next_line:

        and     byte ptr[esi],0

        push    512
        push    esi
        call    _read_text

        mov     ebp,esp

        sub     eax,2                   ; pozbywamy sie CRLF z rozmiaru

        mov     edi,esi
        mov     ecx,eax
        shr     ecx,2

        push    0A0Dh                   ; wstaw znak nowej linii na koncu stringa

        mov     ebx,esp                 ; poczatek zreversowanego stringa
        sub     ebx,eax

@@:     mov     edx,dword ptr[edi]
        add     edi,4

        bswap   edx
        push    edx

        test    ecx,ecx
        je      @f
        dec     ecx
        jmp     @b
@@:
        sub     eax,-2

        push    eax
        push    ebx
        call    _write_text

        mov     esp,ebp

        jmp     _read_next_line


; zakoncz proces
_ctrlc_handler:

        push    0
        call    ExitProcess



_write_text proc lpszString:dword, dwLen:dword

        local   dwWritten:dword

        lea     eax,dwWritten

        push    0
        push    eax
        push    dwLen
        push    lpszString
        push    hConsoleOut
        call    WriteConsoleA

        ret

_write_text endp


_read_text proc uses ebx, lpszString:dword, dwLen:dword

        local   dwRead:dword

        lea     ebx,dwRead
        and     dword ptr[ebx],0

        push    0
        push    ebx
        push    dwLen
        push    lpszString
        push    hConsoleIn
        call    ReadConsoleA

        mov     eax,dword ptr[ebx]

        ret

_read_text endp

end start

Inna wariacja z rekurencją i stosem

.686
.mmx
.model flat,stdcall

include \masm32\include\windows.inc
include \masm32\include\kernel32.inc
include \masm32\include\user32.inc

includelib \masm32\lib\kernel32.lib
includelib \masm32\lib\user32.lib

extern __ImageBase:near

.data
        szCRLF          db 13,10

.data?
        hConsoleOut     dd ?
        hConsoleIn      dd ?

        dwRead          dd ?

        dwConsoleMode   dd ?
.code

start:

; pobierz uchwyty out/in
        push    STD_OUTPUT_HANDLE
        call    GetStdHandle
        mov     hConsoleOut,eax

        push    STD_INPUT_HANDLE
        call    GetStdHandle
        mov     hConsoleIn,eax

; wlacz wprowadzanie znak po znaku
        push    offset dwConsoleMode
        push    hConsoleIn
        call    GetConsoleMode

        mov     eax,dwConsoleMode
        and     eax,not (ENABLE_LINE_INPUT or ENABLE_ECHO_INPUT)

        push    eax
        push    hConsoleIn
        call    SetConsoleMode

; ustaw handler
        push    1
        push    offset _ctrlc_handler
        call    SetConsoleCtrlHandler

        mov     edi,offset dwRead
        mov     esi,offset WriteConsoleA

@@:     call    _process_text
        call    _new_line

        jmp     @b

; zakoncz proces
_ctrlc_handler:

        push    0
        call    ExitProcess

_process_text proc

        push    0
        mov     ebx,esp

        push    0
        push    edi ;offset dwRead
        push    1
        push    ebx
        push    hConsoleOut
        push    offset _ret_free
        push    esi ;offset WriteConsoleA

        push    0
        push    edi ;offset dwRead
        push    1
        push    ebx
        push    hConsoleIn
        call    ReadConsoleA

        cmp     byte ptr[ebx],0Dh
        je      _ret_crlf

        push    0
        push    edi ;offset dwRead
        push    1
        push    ebx
        push    hConsoleOut
        call    esi ;WriteConsoleA

        call    _process_text

        ret
_ret_free:

        pop     eax
        ret

_ret_crlf:

        jmp     _new_line

_process_text endp

_new_line proc

        push    0
        push    edi ;offset dwRead
        push    2
        push    offset szCRLF
        push    hConsoleOut
        call    esi ;WriteConsoleA

        ret

_new_line endp

end start
 

Całkiem ciekawy kod, niezła robota. Wibowita chyba coś wciągnęło, przyjdzie to po mnie poprawi, pisane na sucho, bez testowania - mniej formalna wersja kodu funkcyjnego na kontynuacjach, w Scali:

object Main extends Application {
  def printReversedStdinLn(cont: => Unit) {
    readChar match {
      case '\n' => cont
      case char => printReversedStdinLn { print(char); cont }
    }
  }
  printReversedStdinLn { print('\n') }
}

void re(){
        char z;
        if ((z=getchar()) > '\n') {
                re();
                putchar(z);
        }
}

No niestety readChar w Scali jednak koślawo działa, trzeba posłużyć się rzutowaniem :P

object Main extends Application {

  def printReversedStdinLn(cont: => Unit) {
    System.in.read.asInstanceOf[Char] match {
      case '\n' => cont
      case char => printReversedStdinLn { print(char); cont }
    }
  }
  printReversedStdinLn { print('\n') }
}

Swoją drogą, to jeśli chodzi o kontynuacje to dla Scali jest specjalny framework i chodziło mi o to, że właśnie go nie przerobiłem.

Nie trzeba

def printReversedStdinLn(cont: => Unit) {
  System.in.read match {
    case '\n' => cont
    case char => printReversedStdinLn { System.out.write(char); cont }
  }
}
printReversedStdinLn(println)

readChar tak ma działać, obiekt Console nie wczytuje na zasadzie DataInputStream, ale tak, że jedno read pobiera dane z nowej linii i parsuje (analogicznie jak dla np. readInt()).