Czesc. Mam program do napisania i chcialbym poprosic o jakas pomoc.
Nie do konca rozumiem na jakiej zasadzie dzialaja te listy jednokierunkowe. Czy powinienem zadeklarowac pierwszy i nastepny element. Jesli tak to gdzie itp. Prosze o jakies wskazowki, jestem mega poczatkujacy. Oto tresc:
Z gory thx.
PS Bede wrzucal tutaj to co samemu uda mi sie napisac.
W Javie nie ma wskaznikow, ja mam stos (gdzies znalazlem, kod nie jest moj) w C++, moge sie podzielic, moze w jakis sposob to Ci pomoze :)
#include <iostream>
#include <stdlib.h>
using namespace std;
class Node
{
int liczba;
Node *next;
public:
Node (int i) { liczba = i; next = NULL;}
int Liczba () { return liczba; }
Node *Next () { return next; }
void changeNext (Node *n) { next = n; }
};
class Stack
{
Node *S;
public:
Stack () { S = NULL; }
~Stack ();
void addNode (int i); //dodaje element na stos
int removeNode (); //usuwa element ze stosu
int returnTop (); //zwraca wartość z wierzchołka stosu
bool isEmpty (); //sprawdza, czy stos jest pusty
void printStack (); //wypisuje elementy stosu
};
Stack::~Stack (){
Node *q;
while (!isEmpty())
{
q = S;
S = S -> Next();
delete q;
}
}
void Stack::addNode (int i){ //dodaje element na stos
Node *q;
q = new Node (i);
q -> changeNext (S);
S = q;
}
int Stack::removeNode (){ //usuwa element ze stosu
int liczba;
Node *q;
q = S;
liczba = q -> Liczba();
S = S -> Next ();
delete q;
return liczba;
}
int Stack::returnTop (){ //zwraca wartość z wierzchołka stosu
return S -> Liczba();
}
bool Stack::isEmpty (){ //sprawdza, czy stos jest pusty
if (S == NULL) return 1;
else return 0;
}
void Stack::printStack (){ //wypisuje elementy stosu
Stack temp;
int l;
while (!isEmpty())
{
l = removeNode();
temp.addNode (l);
}
cout << "\n\nElementy stosu:\n";
while (!temp.isEmpty())
{
l = temp.removeNode();
cout << l << endl;
addNode (l);
}
}
int main ()
{
Stack stos;
int wybor, liczba;
do
{
cout << "********\n";
cout << "* Stos *\n";
cout << "********\n";
cout << "\n\n1 - dodaj element\n";
cout << "2 - wypisz elementy stosu\n";
cout << "3 - zdejmij element\n";
cout << "4 - wypisz wierzchołek stosu\n";
cout << "0 - wyjscie z programu\n";
cout << "Twoj wybor:\t";
cin >> wybor;
switch (wybor)
{
case 1: cout << "\n\nPodaj liczbe:\t";
cin >> liczba;
stos.addNode (liczba);
break;
case 2: if (!stos.isEmpty()) stos.printStack();
else cout << "\n\nStos jest pusty\n";
system ("PAUSE");
break;
case 3: if (!stos.isEmpty())
{
liczba = stos.removeNode();
cout << "\n\nUsunieta zostala liczba:\t" << liczba << endl;
}
else cout << "\n\nStos jest pusty\n";
system ("PAUSE");
break;
case 4: if (!stos.isEmpty()) cout << "\n\nWierzcholkiem stosu jest wartosc:\t" << stos.returnTop() << endl;
else cout << "\n\nStos jest pusty\n";
system ("PAUSE");
break;
}
system ("CLS");
}
while (wybor != 0);
return 0;
}
Poczytaj sobie w internecie cos o stosie, itp, czasem mozna trafic na dobre wyjasnienie :)
Lol. A bez tego idiotycznego stosu to ok. 8 linijkowa funkcja rekurencyjna...
Wymuszanie szczegółów implementacji w zadaniu jest bezsensowne.
#subnet
Jeszcze nie mialem kontaktu z C, wiec ten kod niewiele mi mowi. (dopiero zaczynam programowac)
#lol^6
Coz, widocznie to zadanie ma wymusic, zebym to przecwiczyl i zrozumial, a to ze mozna je zrobic latwiejszym sposobem to juz inna bajka...
Niech znaki (,{,[ powodują odłożenie na stos odpowiedniego symbolu. Znaki ),},] powodują zdjęcie ze stosu symbolu to wtedy wystarczy przejść się po tablicy znaków w danym stringu i dokładać i zdejmować znaki. Przy zdejmowaniu wystarczy sprawdzać czy znak zdejmujący jest tego samego typu co znak zdejmowany ze stosu. Na koniec stos powinien być pusty.
Napisalem cos takiego...
Klasa StosJakoLista:
import java.util.EmptyStackException;
public class StosJakoLista implements Stos {
boolean czyPusty=false;
public Nawiasy nast;
public Nawiasy pierwszy;
public void naStos(Nawiasy znak) {
}
public boolean pusty() {
if(pierwszy == null){
czyPusty=true;
}
return czyPusty;
}
public Nawiasy zeStosu() throws EmptyStackException {
return null;
}
}
Klasa Nawiasy:
public class Nawiasy {
boolean x=false;
StosJakoLista s = new StosJakoLista();
char dane;
public Nawiasy(){
dane=0;
}
boolean nawiasyZrownowazone(String wyrazenie){
if(s.pusty()==true && wyrazenie!=null){
x=true;
}
return x;
}
boolean nawiasOtwierajacy(char ch){
if(ch=='(' || ch=='[' || ch== '{'){
x=true;
}
return x;
}
boolean nawiasZamykajacy(char ch){
if(ch==')' || ch==']' || ch== '}'){
x=true;
}
return x;
}
}
Interfejs Stos:
import java.util.EmptyStackException;
public interface Stos {
boolean pusty();
void naStos(Nawiasy znak);
Nawiasy zeStosu() throws EmptyStackException;
}
Klasa Main:
import java.io.*;
public class Main {
public static void main(String args[]) throws IOException{
Nawiasy n = new Nawiasy();
StosJakoLista st=new StosJakoLista();
InputStreamReader obin = new InputStreamReader(System.in);
BufferedReader obuf = new BufferedReader(obin);
StreamTokenizer tok = new StreamTokenizer(obuf);
System.out.println("Wprowadz wyrazenie: ");
try{
tok.nextToken();
}
catch(IOException e){
System.out.print("Blad podczas odczytu danych");
return;
}
String wyrazenie=tok.sval;
if(n.nawiasyZrownowazone(wyrazenie)){
System.out.println("To wyrazenie jest zrownowazone. ");
}
else{
System.out.println("To wyrazenie nie jest zrownowazone. ");
}
}
}
Czy moglby ktos sprawdzic to co napisalem? Nie potrafie napisac metody zeStosu, pomozecie mi?
Teraz mam cos takiego:
Klasa Nawiasy:
public class Nawiasy {
boolean x=false;
StosJakoLista s = new StosJakoLista();
ElementStosu e = new ElementStosu();
boolean nawiasyZrownowazone(String wyrazenie){
if(s.pusty()==true && wyrazenie!=null){
x=true;
}
return x;
}
boolean nawiasOtwierajacy(char ch){
if(e.dane=='(' || e.dane=='[' || e.dane== '{'){
x=true;
}
return x;
}
boolean nawiasZamykajacy(char ch){
if(e.dane==')' || e.dane==']' || e.dane== '}'){
x=true;
}
return x;
}
}
Interfejs Stos:
import java.util.EmptyStackException;
public interface Stos {
boolean pusty();
char naStos(char znak);
char zeStosu() throws EmptyStackException;
}
Klasa ElementStosu:
public class ElementStosu {
ElementStosu nast;
char dane;
public ElementStosu(){
dane=0;
nast=null;
}
}
Klasa StosJakoLista:
import java.util.EmptyStackException;
public class StosJakoLista implements Stos {
boolean czyPusty=false;
private ElementStosu head;
private int length = 0;
public StosJakoLista(){
head=null;
length=0;
}
ElementStosu pomoc = new ElementStosu();
public char naStos(char nawias) {
length++;
if(head==null){
head = new ElementStosu();
nawias = head.dane;
head.nast=new ElementStosu();
}
else{
head.nast=pomoc;
pomoc.dane=nawias;
pomoc.nast=new ElementStosu();
}
return nawias;
}
public boolean pusty() {
if(head == null){
czyPusty=true;
}
return czyPusty;
}
public char zeStosu() throws EmptyStackException {
(tutaj nie wiem za bardzo co zrobic)
}
}
Klasa Main:
import java.io.*;
public class Main {
public static void main(String args[]) throws IOException{
String wyrazenie=null;
StosJakoLista st=new StosJakoLista();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
ElementStosu el = new ElementStosu();
Nawiasy n = new Nawiasy();
System.out.println("Wprowadz wyrazenie: ");
try{
wyrazenie=br.readLine();
}
catch(IOException e){
System.out.print("Blad podczas odczytu danych");
return;
}
char[] tab = wyrazenie.toCharArray();
for(int i=0; i<tab.length; i++){
if(tab[i]=='('){
st.naStos('(');
if(tab[i]==')'){
st.zeStosu();
}
}
if(tab[i]=='['){
st.naStos('[');
if(tab[i]==']'){
st.zeStosu();
}
}
if(tab[i]=='{'){
st.naStos('{');
if(tab[i]=='}'){
st.zeStosu();
}
}
}
if(wyrazenie==null){
System.out.println("Blad. ");
}
else{
if(n.nawiasyZrownowazone(wyrazenie)){
System.out.println("To wyrazenie jest zrownowazone. ");
}
else{
System.out.println("To wyrazenie nie jest zrownowazone. ");
}
}
}
}
PS ten "zaifowany" main tez nie wyglada chyba dobrze..
Czy moglibyscie pomoc? Na dzisiaj mialem ten program i go nie oddalem... mimo ze duzo czasu na niego poswiecilem. Czy moglby mi ktos sprawdzic to co mam i pomoc w napisaniu metod naStos i zeStosu?
package net.forum4programmers;
public interface Stos {
boolean pusty();
char naStos(final char c);
char zeStosu();
}
package net.forum4programmers;
import java.util.Stack;
public class StosJakoLista extends Stack<Character> implements Stos {
private static final long serialVersionUID = 6744294375517214708L;
@Override
public char naStos(char c) {
return this.push(c);
}
@Override
public boolean pusty() {
return this.isEmpty();
}
@Override
public char zeStosu() {
return this.pop();
}
}
package net.forum4programmers;
import java.util.HashMap;
public class Nawiasy {
private final static HashMap<Character, Character> brackets =
new HashMap<Character, Character>();
static {
brackets.put('(', ')');
brackets.put('[', ']');
brackets.put('{', '}');
}
private final Stos stack = new StosJakoLista();
public boolean nawiasyZrownowazone(final String wyrazenie) {
char[] chars = wyrazenie.toCharArray();
for (final char c : chars) {
if (this.nawiasOtwierający(c)) {
this.stack.naStos(c);
} else if (this.nawiasZamykajacy(c)) {
if (this.stack.pusty()) {
return false;
} else if (brackets.get(this.stack.zeStosu()) != c) {
return false;
}
}
}
return true;
}
protected boolean nawiasOtwierający(char c) {
return brackets.containsKey(c);
}
protected boolean nawiasZamykajacy(char c) {
return brackets.containsValue(c);
}
/**
* Main - do testu.
*/
public static void main(String[] args) {
String expression1 = "(w*[x+z]/y-[p/{r-q}])";
String expression2 = "(w*[x+z/y-[p/{r-q}])";
final Nawiasy brackets = new Nawiasy();
System.out.println(expression1 + " czy jest zrównoważone " +
brackets.nawiasyZrownowazone(expression1));
System.out.println(expression2 + " czy jest zrównoważone " +
brackets.nawiasyZrownowazone(expression2));
}
}
Wiem, że stos pewnie gość chciał żebyście napisali sami, ale po co pisać coś co już istnieje i jest szeroko dostępne ? Moim zdaniem powinni też nauczać jak szukać.
No wiem.. ale wlasnie chyba o to chodzilo, zebysmy sami napisali, a ja mam klopot z tymi metodami wrzucania na stos i zdejmowania. :(
package net.forum4programmers;
public interface Stos {
boolean pusty();
Character naStos(final char c);
Character zeStosu();
}
public class StosJakoLista implements Stos {
private static final long serialVersionUID = 6744294375517214708L;
private transient Character[] data;
private int size = 0;
/**
* Konstruktor.
*/
public StosJakoLista() {
this(10);
}
/**
* Konstruktor.
*
* @param capacity początkowa pojemność
*/
public StosJakoLista(int capacity) {
this.data = new Character[capacity];
}
@Override
public synchronized Character naStos(char c) {
this.size ++;
this.trimToSize();
this.data[this.size - 1] = c;
return c;
}
private void trimToSize() {
if (this.size >= this.data.length) {
this.data = Arrays.copyOf(this.data, this.size);
}
}
@Override
public synchronized boolean pusty() {
return this.size == 0;
}
@Override
public synchronized Character zeStosu() {
if (!this.pusty()) {
final Character c = this.data[this.size - 1];
this.data[this.size - 1] = null;
this.size --;
return c;
}
return null;
}
public synchronized void czysc() {
for (int i = 0; i < this.data.length; i++) {
this.data[i] = null;
}
this.size = 0;
}
}