1、字符串的反转
import java.io.*;
class StackX
{
private int maxSize;
private char[] stackArray;
private int top;
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);
}
}
//==========================================================
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;
}
}
//==========================================================
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("") ) // quit if [Enter]
break;
Reverser theReverser = new Reverser(input);
output = theReverser.doRev(); // use it
System.out.println("Reversed: " + output);
}
}
public static String getString() throws IOException
{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
}
2、括号匹配
// to run this program: C>java bracketsApp
import java.io.*; // for I/Oclass 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:
break;
} // end switch
} // end for
if( !theStack.isEmpty() )
System.out.println("Error: missing right delimiter");
else
System.out.println("Right");
} // 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;
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
3、算式中缀转后缀
input为中缀表达式，output为后缀表达式
栈中会保存+-*/(，栈底优先级低，栈顶优先级高（不包括括号），在括号内栈底优先级低，栈顶优先级高
遍历input，取某个值i。
i为数字时，直接添加到ouput中。
i为'('时，直接将i push到栈中。
i为'+-*/'时，如果栈不为空，pop栈的值s。
如果s是'('或s为'+-*/'且优先级小于i，则先把s push到栈中，再把i push到栈中。
如果s为'+-*/'且优先级大于等于i，则将s添加到output中，继续pop栈的值比较，直到那个值m的
优先级小于i或栈为空为止，最后将m push到栈中，再将i push到栈中。
i为')'时，pop栈的值s
如果s是'('，则什么也不做
如果s值其它值，则添加到output中，继续pop栈的值，直到pop的值为'('。
// to run this program: C>java InfixApp
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); }
public int size() // return size
{ return top+1; }
public char peekN(int n) // return item at index n
{ return stackArray[n]; }
public void displayStack(String s)
{
System.out.print(s);
System.out.print("Stack (bottom-->top): ");
for(int j=0; j<size(); j++)
{
System.out.print( peekN(j) );
System.out.print("");
}
System.out.println("");
}
} // end class StackX
//============================================================
class InToPost // infix to postfix conversion
{
private StackX theStack;
private String input;
private String output = "";
public InToPost(String in) // constructor
{
input = in;
int stackSize = input.length();
theStack = new StackX(stackSize);
}
//--------------------------------------------------------------
public String doTrans() // do translation to postfix
{
for(int j=0; j<input.length(); j++) // for each char
{
char ch = input.charAt(j); // get it
theStack.displayStack("For "+ch+" "); // *diagnostic*
switch(ch)
{
case '+': // it's + or -
case '-':
gotOper(ch, 1); // go pop operators
break; // (precedence 1)
case '*': // it's * or /
case '/':
gotOper(ch, 2); // go pop operators
break; // (precedence 2)
case '(': // it's a left paren
theStack.push(ch); // push it
break;
case ')': // it's a right paren
gotParen(ch); // go pop operators
break;
default: // must be an operand
output = output + ch; // write it to output
break;
} // end switch
} // end for
while( !theStack.isEmpty() ) // pop remaining opers
{
theStack.displayStack("While "); // *diagnostic*
output = output + theStack.pop(); // write to output
}
theStack.displayStack("End "); // *diagnostic*
return output; // return postfix
} // end doTrans()
//--------------------------------------------------------------
public void gotOper(char opThis, int prec1)
{ // got operator from input
while( !theStack.isEmpty() )
{
char opTop = theStack.pop();
if( opTop == '(' ) // if it's a '('
{
theStack.push(opTop); // restore '('
break;
}
else // it's an operator
{
int prec2; // precedence of new op
if(opTop=='+' || opTop=='-') // find new op prec
prec2 = 1;
else
prec2 = 2;
if(prec2 < prec1) // if prec of new op less
{ // than prec of old
theStack.push(opTop); // save newly-popped op
break;
}
else // prec of new not less
output = output + opTop; // than prec of old
} // end else (it's an operator)
} // end while
theStack.push(opThis); // push new operator
} // end gotOp()
public void gotParen(char ch)
{ // got right paren from input
while( !theStack.isEmpty() )
{
char chx = theStack.pop();
if( chx == '(' ) // if popped '('
break; // we're done
else // if popped operator
output = output + chx; // output it
} // end while
} // end popOps()
} // end class InToPost
//===============================================================
class InfixApp
{
public static void main(String[] args) throws IOException
{
String input, output;
while(true)
{
System.out.print("Enter infix: ");
System.out.flush();
input = getString(); // read a string from kbd
if( input.equals("") ) // quit if [Enter]
break;
InToPost theTrans = new InToPost(input);
output = theTrans.doTrans(); // do the translation
System.out.println("Postfix is " + output + '
');
} // 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 InfixApp
4、后缀表达式求值
操作数->入栈
操作符->从栈中提出两个操作数，用操作符将其执行运算。结果入栈。
// to run this program: C>java PostfixApp
import java.io.*; // for I/Oclass StackX
{
private int maxSize;
private int[] stackArray;
private int top;
//--------------------------------------------------------------
public StackX(int size) // constructor
{
maxSize = size;
stackArray = new int[maxSize];
top = -1;
}
//--------------------------------------------------------------
public void push(int j) // put item on top of stack
{ stackArray[++top] = j; }
//--------------------------------------------------------------
public int pop() // take item from top of stack
{ return stackArray[top--]; }
//--------------------------------------------------------------
public int peek() // peek at top of stack
{ return stackArray[top]; }
//--------------------------------------------------------------
public boolean isEmpty() // true if stack is empty
{ return (top == -1); }
//--------------------------------------------------------------
public boolean isFull() // true if stack is full
{ return (top == maxSize-1); }
//--------------------------------------------------------------
public int size() // return size
{ return top+1; }
//--------------------------------------------------------------
public int peekN(int n) // peek at index n
{ return stackArray[n]; }
//--------------------------------------------------------------
public void displayStack(String s)
{
System.out.print(s);
System.out.print("Stack (bottom-->top): ");
for(int j=0; j<size(); j++)
{
System.out.print( peekN(j) );
System.out.print(' ');
}
System.out.println("");
}
//--------------------------------------------------------------
} // end class StackXclass ParsePost
{
private StackX theStack;
private String input;
//--------------------------------------------------------------
public ParsePost(String s)
{ input = s; }
//--------------------------------------------------------------
public int doParse()
{
theStack = new StackX(20); // make new stack
char ch;int num1, num2, interAns;
for(int j=0; j<input.length(); j++) // for each char,
{
ch = input.charAt(j); // read from input
theStack.displayStack(""+ch+" "); // *diagnostic*
if(ch >= '0' && ch <= '9') // if it's a number
theStack.push( (int)(ch-'0') ); // push it
else // it's an operator
{
num2 = theStack.pop(); // pop operands
num1 = theStack.pop();
switch(ch) // do arithmetic
{
case '+':
interAns = num1 + num2;
break;
case '-':
interAns = num1 - num2;
break;
case '*':
interAns = num1 * num2;
break;
case '/':
interAns = num1 / num2;
break;
default:
interAns = 0;
} // end switch
theStack.push(interAns); // push result
} // end else
} // end for
interAns = theStack.pop(); // get answer
return interAns;
} // end doParse()
} // end class ParsePost
////////////////////////////////////////////////////////////////
class PostfixApp
{
public static void main(String[] args) throws IOException
{
String input;
int output;
while(true)
{
System.out.print("Enter postfix: ");
System.out.flush();
input = getString(); // read a string from kbd
if( input.equals("") ) // quit if [Enter]
break;
ParsePost aParser = new ParsePost(input);
output = aParser.doParse(); // do the evaluation
System.out.println("Evaluates to " + output);
} // 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 PostfixApp
5、栈的链表实现
// to run this program: C>java LinkStackApp
class Link
{
public long dData; // data item
public Link next; // next link in list
public Link(long dd) // constructor
{ dData = dd; }
public void displayLink() // display ourself
{ System.out.print(dData + " "); }
}
//==============================================================
class LinkList
{
private Link first; // ref to first item on list
public LinkList() // constructor
{ first = null; } // no items on list yet
public boolean isEmpty() // true if list is empty
{ return (first==null); }
public void insertFirst(long dd) // insert at start of list
{ // make new link
Link newLink = new Link(dd);
newLink.next = first; // newLink --> old first
first = newLink; // first --> newLink
}
public Long deleteFirst() // delete first item
{ // (assumes list not empty)
if(!isEmpty())
{
Link temp = first;
first = first.next;
return temp.dData;
}
else
return null;
}
public void displayList()
{
Link current = first; // start at beginning of list
while(current != null) // until end of list,
{
current.displayLink(); // print data
current = current.next; // move to next link
}
System.out.println("");
}
}
//==============================================================
class LinkStack
{
private LinkList theList;
public LinkStack() // constructor
{
theList = new LinkList();
}
public void push(long j) // put item on top of stack
{
theList.insertFirst(j);
}
public Long pop() // take item from top of stack
{
return theList.deleteFirst();
}
public boolean isEmpty() // true if stack is empty
{
return ( theList.isEmpty() );
}
public void displayStack()
{
System.out.print("Stack (top-->bottom): ");
theList.displayList();
}
}
//==============================================================
class LinkStackApp
{
public static void main(String[] args)
{
LinkStack theStack = new LinkStack(); // make stack
theStack.push(20); // push items
theStack.push(40);
theStack.displayStack(); // display stack
theStack.push(60); // push items
theStack.push(80);
theStack.displayStack(); // display stack
theStack.pop(); // pop items
theStack.pop();
theStack.displayStack(); // display stack
}
}