javaデータ構造におけるスタック構造アプリケーションの2つの例
javaデータ構造におけるスタック構造アプリケーションの2つの例
1、単語逆順。
コンソールから文字列を読み込む必要があります。回車で入力を終了し、逆順文字列を表示します。
順序を逆にする操作には、スタックで解決するのが便利です。具体的な考えは、文字列の各文字を順番にスタックに入れて、もう一つの文字をスタックから取り出すことです。このときは逆順で取り出した文字列です。
いくつかのセパレータは、プログラム中に必ずペアとして現れます。例えば（）、{}と[]などです。マッチしていないセパレータが発見された場合、コンパイラはエラーを報告します。マッチング操作は近くの原則をとるため、後から入力する分割子は優先的にマッチし、「後進先出」の特徴があります。この整合動作はスタックで実現できる。
具体的な動作は、入力中に左のマッチがあったら、左のマッチをスタックに押し込むことである。右の一致子がある場合、スタックからデータを取り出し、右の一致子と一致するかどうかを分析する。マッチする場合は続行します。マッチしない場合はエラー終了します。
1、単語逆順。
コンソールから文字列を読み込む必要があります。回車で入力を終了し、逆順文字列を表示します。
順序を逆にする操作には、スタックで解決するのが便利です。具体的な考えは、文字列の各文字を順番にスタックに入れて、もう一つの文字をスタックから取り出すことです。このときは逆順で取り出した文字列です。
// reverse.java
// stack used to reverse a string
// to run this program: C>java ReverseApp
import java.io.*; // for I/O
////////////////////////////////////////////////////////////////
class StackX//
{
private int maxSize;//
private char[] stackArray;//
private int top;// ， 0
//--------------------------------------------------------------
public StackX(int max) // constructor
{
maxSize = max;
stackArray = new char[maxSize];
top = -1;
}
//--------------------------------------------------------------
public void push(char j) // put item on top of stack
{
stackArray[++top] = j;
}
//--------------------------------------------------------------
public char pop() // take item from top of stack
{
return stackArray[top--];
}
//--------------------------------------------------------------
public char peek() // peek at top of stack
{
return stackArray[top];
}
//--------------------------------------------------------------
public boolean isEmpty() // true if stack is empty
{
return (top == -1);
}
//--------------------------------------------------------------
} // end class StackX
////////////////////////////////////////////////////////////////
class Reverser//
{
private String input; // input string
private String output; // output string
//--------------------------------------------------------------
public Reverser(String in) // constructor
{ input = in; }
//--------------------------------------------------------------
public String doRev() // reverse the string
{
int stackSize = input.length(); // get max stack size
StackX theStack = new StackX(stackSize); // make stack
for(int j=0; j<input.length(); j++)
{
char ch = input.charAt(j); // get a char from input
theStack.push(ch); // push it
}
output = "";
while( !theStack.isEmpty() )
{
char ch = theStack.pop(); // pop a char,
output = output + ch; // append to output
}
return output;
} // end doRev()
//--------------------------------------------------------------
} // end class Reverser
////////////////////////////////////////////////////////////////
class ReverseApp
{
public static void main(String[] args) throws IOException
{
String input, output;
while(true)
{
System.out.print("Enter a string: ");
System.out.flush();
input = getString(); // read a string from kbd
if( input.equals("") ) // ，
break;
// make a Reverser
Reverser theReverser = new Reverser(input);
output = theReverser.doRev(); // use it
System.out.println("Reversed: " + output);
} // end while
System.out.println("this is end");
} // end main()
//--------------------------------------------------------------
public static String getString() throws IOException
{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
//--------------------------------------------------------------
} // end class ReverseApp
////////////////////////////////////////////////////////////////
いくつかのセパレータは、プログラム中に必ずペアとして現れます。例えば（）、{}と[]などです。マッチしていないセパレータが発見された場合、コンパイラはエラーを報告します。マッチング操作は近くの原則をとるため、後から入力する分割子は優先的にマッチし、「後進先出」の特徴があります。この整合動作はスタックで実現できる。
具体的な動作は、入力中に左のマッチがあったら、左のマッチをスタックに押し込むことである。右の一致子がある場合、スタックからデータを取り出し、右の一致子と一致するかどうかを分析する。マッチする場合は続行します。マッチしない場合はエラー終了します。
// brackets.java
// stacks used to check matching brackets
// to run this program: C>java bracketsApp
import java.io.*; // for I/O
////////////////////////////////////////////////////////////////
class StackX
{
private int maxSize;
private char[] stackArray;
private int top;
//--------------------------------------------------------------
public StackX(int s) // constructor
{
maxSize = s;
stackArray = new char[maxSize];
top = -1;
}
//--------------------------------------------------------------
public void push(char j) // put item on top of stack
{
stackArray[++top] = j;
}
//--------------------------------------------------------------
public char pop() // take item from top of stack
{
return stackArray[top--];
}
//--------------------------------------------------------------
public char peek() // peek at top of stack
{
return stackArray[top];
}
//--------------------------------------------------------------
public boolean isEmpty() // true if stack is empty
{
return (top == -1);
}
//--------------------------------------------------------------
} // end class StackX
////////////////////////////////////////////////////////////////
class BracketChecker
{
private String input; // input string
//--------------------------------------------------------------
public BracketChecker(String in) // constructor
{ input = in; }
//--------------------------------------------------------------
public void check()
{
int stackSize = input.length(); // get max stack size
StackX theStack = new StackX(stackSize); // make stack
for(int j=0; j<input.length(); j++) // get chars in turn
{
char ch = input.charAt(j); // get char
switch(ch)
{
case '{': // opening symbols
case '[':
case '(':
theStack.push(ch); // push them
break;
case '}': // closing symbols
case ']':
case ')':
if( !theStack.isEmpty() ) // if stack not empty,
{
char chx = theStack.pop(); // pop and check
if( (ch=='}' && chx!='{') ||
(ch==']' && chx!='[') ||
(ch==')' && chx!='(') )//
System.out.println("Error: "+ch+" at "+j);
}
else // prematurely empty
System.out.println("Error: "+ch+" at "+j);
break;
default: // no action on other characters
break;
} // end switch
} // end for
// at this point, all characters have been processed
if( !theStack.isEmpty() )
System.out.println("Error: missing right delimiter");
} // end check()
//--------------------------------------------------------------
} // end class BracketChecker
////////////////////////////////////////////////////////////////
class BracketsApp
{
public static void main(String[] args) throws IOException
{
String input;
while(true)
{
System.out.print(
"Enter string containing delimiters: ");
System.out.flush();
input = getString(); // read a string from kbd
if( input.equals("") ) // quit if [Enter]
break;
// make a BracketChecker
BracketChecker theChecker = new BracketChecker(input);
theChecker.check(); // check brackets
} // end while
} // end main()
//--------------------------------------------------------------
public static String getString() throws IOException
{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
//--------------------------------------------------------------
} // end class BracketsApp
////////////////////////////////////////////////////////////////