此文章介绍关于顺序栈，链式栈的实例操作，括号匹配，表达式求值（后缀表达式）
package ch05; public interface SStack <T>{ boolean isEmpty(); // 判断栈是否为空 void push(T x); // 元素x入栈 T pop(); // 出栈，返回栈顶元素 T peek(); // 返回栈顶元素，但不出栈 }
2. 定义顺序栈类SeqStack<T>，包括数据元素的对象数组和栈顶元素下标两个私有成员变量，构造方法可实例化容量为size大小的空顺序栈，调用类中成员方法实现顺序栈的入栈、出栈、获取栈顶元素等操作，重写toString()方法获取顺序栈的字符串描述。
package ch05;
public class SeqStack <T> implements SStack<T>{
Object[] element;
int top;
// 构造方法，创建一个空栈，存储容量大小size
public SeqStack(int size){
element=new Object[size];
top=-1;
}
// 判断栈是否为空
@Override
public boolean isEmpty() {
return top==-1;
}
// 元素x入栈
@Override
public void push(T x) {
if (x==null){
return;
}
// 若栈满，则扩充栈容量
if (this.top==element.length-1){
Object[] temp=this.element;
element=new Object[temp.length*2];
for (int i=0;i<temp.length;i++){
element[i]=temp[i];
}
}
//入栈
this.element[++top]=x;
}
// 出栈，返回栈顶元素
@Override
public T pop() {
if (top!=-1){
return (T) this.element[this.top--];
}
return null;
}
// 返回栈顶元素，但不出栈
@Override
public T peek() {
if (top!=-1){
return (T) this.element[this.top];
}
return null;
}
// 返回顺序栈中所有元素的描述字符串，形式为\"（,）\"，覆盖Object类的toString()方法
public String toString(){// 自栈顶输出到栈底
String str=\"\";
if (top>=0){
str=\"(\";
for (int i=top;i>=0;i--){
str+=element[i]+\",\";
}
str=str.substring(0,str.length()-1);
str+=\")\";
}else {//空栈
str=\"()\";
}
return str;
}
}
3.定义结点类Node<T>，包括数据域和地址域两个成员变量，构造方法实例化结点，重写toString()方法获取结点的字符串描述。
package ch05;
public class Node <T>{
public T data;
public Node<T> next;
public Node(T data, Node<T> next) {
this.data = data;
this.next = next;
}
public Node(){
this(null,null);
}
}
4. 定义链式栈类LinkedStack<T>：
package ch05;
public class LinkedStack<T> implements SStack<T>{
private Node<T> top;
public LinkedStack() {
top=new Node<>();
}
@Override
public boolean isEmpty() {
return top.next==null ? true:false;
}
@Override
public void push(T x) {
if (x==null){
return;
}
//生成新结点
Node<T> q=new Node<>(x,null);
q.next=top.next;
top.next=q;
}
@Override
public T pop() {
T elem=null;
if (top.next!=null){
elem=top.next.data;
top.next=top.next.next;
}
return elem;
}
@Override
public T peek() {
T elem=null;
if (top.next!=null){
elem=top.next.data;
}
return elem;
}
// 返回顺序栈中所有元素的描述字符串，形式为\"（,）\"，覆盖Object类的toString()方法
public String toString(){
String str=\"\";
Node<T> p=top.next;
if (p!=null){
str=\"(\";
while (p!=null){
str+=p.data+\",\";
p=p.next;
}
str=str.substring(0,str.length()-1);
str+=\")\";
}else {
str=\"()\";
}
return str;
}
}
5.括号匹配
package ch07;
import java.util.Scanner;
public class Bracket {
// 括号匹配
public static String isMatched(String infix) {
SeqStack<Character> stack = new SeqStack<Character>(infix.length());
for (int i = 0; i < infix.length(); i++) {
char ch = infix.charAt(i);
switch (ch) {
case \'(\':
stack.push(ch);
break;
case \')\':
if (stack.isEmpty() || !stack.pop().equals(\'(\')) {
return \"expect (\";
}
}
}
return stack.isEmpty() ? \"\" : \"expect )\";
}
// 测试括号匹配算法
public static void main(String[] args) {
// 括号匹配
Scanner r = new Scanner(System.in);
System.out.print(\"输入括号表达式：\");
String infix = r.nextLine();
System.out.println(isMatched(infix));
}
}
6.表达式求值（后缀表达式）：
package ch05;
import java.util.Scanner;
public class ExpressionPoland {
// 括号匹配
public static String isMatched(String infix) {
SeqStack<Character> stack = new SeqStack<Character>(infix.length());
for (int i = 0; i < infix.length(); i++) {
char ch = infix.charAt(i);
switch (ch) {
case \'(\':
stack.push(ch);
break;
case \')\':
if (stack.isEmpty() || !stack.pop().equals(\'(\')) {
return \"expect (\";
}
}
}
return stack.isEmpty() ? \"\" : \"expect )\";
}
// 将中缀表达式转换为后缀表达式
public static StringBuffer toPostfix(String infix){
SeqStack<Character> stack=new SeqStack<Character>(infix.length());
StringBuffer postfix=new StringBuffer(infix.length()*2);
int i=0;
System.out.println(\"\\n求后缀表达式过程：\");
System.out.println(\"字符\"+\"\\tstack\\t\\tpostfix\");
while(i<infix.length()){ // 对表达式中的每个字符进行处理
char ch=infix.charAt(i); // 第i个字符
System.out.print(ch+\"\\t\"); // 输出第i个字符
switch(ch){ // 判断字符类别
// +、-运算符
case \'+\':
case \'-\':
// 当栈不空且栈顶运算符优先级高时，包括+、-、*、/
while(!stack.isEmpty() && !stack.peek().equals(\'(\')){ // 栈中的\'(\'优先级最低
postfix.append(stack.pop()+\" \"); // 将出栈的运算符追加到后缀表达式中（空格间隔）
}
stack.push(ch); // 第i个字符入栈
i++;
break;
case \'*\':
case \'/\':
// 当栈不空且栈顶运算符优先级高时，包括*、/
while(!stack.isEmpty() && (stack.peek().equals(\'*\') || stack.peek().equals(\'/\'))){
postfix.append(stack.pop()+\" \"); // 将出栈的运算符追加到后缀表达式中（空格间隔）
}
stack.push(ch); // 第i个字符入栈
i++;
break;
case \'(\':
stack.push(ch); // \'(\'入栈
i++;
break;
case \')\':
Character out=stack.pop();
while(out!=null && !out.equals(\'(\')){ // 若干运算符出栈，直到\'(\'出栈
postfix.append(out+\" \"); // 将出栈的运算符追加到后缀表达式中（空格间隔）
out=stack.pop();
}
i++;
break;
default:
while(i<infix.length() && ch>=\'0\' && ch<=\'9\'){ // 获取运算的整数
postfix.append(ch); // 将数字追加到后缀表达式中
i++;
if(i<infix.length()){
ch=infix.charAt(i); // 下一位字符
}
}
postfix.append(\" \"); // 运算数以空格间隔
}
System.out.printf(\"%-18s\",stack.toString()); // 输出每个运算符或运算数处理后栈中的内容
System.out.println(postfix); // 输出每个运算符或运算数处理后的后缀表达式
}
while(!stack.isEmpty()){ // 栈中运算符全部出栈
postfix.append(stack.pop());
}
return postfix;
}
// 计算后缀表达式的值
public static int toValue(StringBuffer postfix){
LinkedStack<Integer> stack=new LinkedStack<Integer>();
int value=0;
System.out.println(\"\\n计算过程：\");
for(int i=0;i<postfix.length();i++){
char ch=postfix.charAt(i);
if(ch>=\'0\' && ch<=\'9\'){
String s=\"\";
while(ch!=\' \'){// 求运算数
s+=ch;
i++;
ch=postfix.charAt(i);
}
stack.push(Integer.parseInt(s)); // 将运算数入栈
}else{
if(ch!=\' \'){
int y=stack.pop(); // 第二个运算数
int x=stack.pop(); // 第一个运算数
switch(ch){
case \'+\':
value=x+y;
break;
case \'-\':
value=x-y;
break;
case \'*\':
value=x*y;
break;
case \'/\':
value=x/y;
break;
}//switch
// 输出计算表达式
if(y>=0){
System.out.println(x+(ch+\"\")+y+\"=\"+value);
}else{
System.out.println(x+(ch+\"\")+\"(\"+y+\")\"+\"=\"+value);
}
// 计算结果入栈
stack.push(value);
}
}
}
return stack.pop(); // 返回栈中计算的最终结果
}
// 测试表达式求值算法
public static void main(String[] args) {
Scanner r=new Scanner(System.in);
// 表达式求值
System.out.print(\"输入表达式：\");
String infix = r.nextLine();
String match=isMatched(infix);
if(match.equals(\"\")){// 括号匹配
StringBuffer postfix=toPostfix(infix);
System.out.println(\"\\n后缀表达式:\"+postfix);
System.out.println(\"\\n计算结果：\"+toValue(postfix));
}else{// 括号不匹配
System.out.println(\"表达式错误：\"+match);
}
}
}
运行结果如下：
做猪小侠源码的代理，提供一站式服务
如果你不懂得搭建网站或者服务器，小程序，源码之类的怎么办？ 第一通过本站学习各种互联网的技术 第二就是联系客服，我帮帮你搭建（当然要收取部分的费用） 第三成为我们的代理，我们提供整套的服务。