java数据结构关于栈的实例应用

java数据结构关于栈的实例应用

此文章介绍关于顺序栈，链式栈的实例操作，括号匹配，表达式求值（后缀表达式）

1.声明一个栈接口SStack

package ch05;

public interface SStack {

boolean isEmpty(); // 判断栈是否为空

void push(T x); // 元素x入栈

T pop(); // 出栈，返回栈顶元素

T peek(); // 返回栈顶元素，但不出栈

}

2.定义顺序栈类SeqStack，包括数据元素的对象数组和栈顶元素下标两个私有成员变量，构造方法可实例化容量为size大小的空顺序栈，调用类中成员方法实现顺序栈的入栈、出栈、获取栈顶元素等操作，重写toString()方法获取顺序栈的字符串描述。

package ch05;

public class SeqStack implements SStack{

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

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，包括数据域和地址域两个成员变量，构造方法实例化结点，重写toString()方法获取结点的字符串描述。

package ch05;

public class Node {

public T data;

public Node next;

public Node(T data, Node next) {

this.data = data;

this.next = next;

}

public Node(){

this(null,null);

}

}

4.定义链式栈类LinkedStack：

package ch05;

public class LinkedStack implements SStack{

private Node 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 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 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 stack = new SeqStack(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 stack = new SeqStack(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 stack=new SeqStack(infix.length());

StringBuffer postfix=new StringBuffer(infix.length()*2);

int i=0;

System.out.println("\n求后缀表达式过程：");

System.out.println("字符"+"\tstack\t\tpostfix");

while(i

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 '/':

http:// // 当栈不空且栈顶运算符优先级高时，包括*、/

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='0' && ch<='9'){ // 获取运算的整数

postfix.append(ch); // 将数字追加到后缀表达式中

i++;

if(i

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 stack=new LinkedStack();

int value=0;

System.out.println("\n计算过程：");

for(int i=0;i

char ch=postfix.charAt(i);

if(ch>='0' && ch<='9')yAAKlrp{

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);

}

}

}

运行结果如下：

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，包括数据域和地址域两个成员变量，构造方法实例化结点，重写toString()方法获取结点的字符串描述。

package ch05;

public class Node {

public T data;

public Node next;

public Node(T data, Node next) {

this.data = data;

this.next = next;

}

public Node(){

this(null,null);

}

}

4.定义链式栈类LinkedStack：

package ch05;

public class LinkedStack implements SStack{

private Node 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 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 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 stack = new SeqStack(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 stack = new SeqStack(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 stack=new SeqStack(infix.length());

StringBuffer postfix=new StringBuffer(infix.length()*2);

int i=0;

System.out.println("\n求后缀表达式过程：");

System.out.println("字符"+"\tstack\t\tpostfix");

while(i

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 '/':

http:// // 当栈不空且栈顶运算符优先级高时，包括*、/

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='0' && ch<='9'){ // 获取运算的整数

postfix.append(ch); // 将数字追加到后缀表达式中

i++;

if(i

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 stack=new LinkedStack();

int value=0;

System.out.println("\n计算过程：");

for(int i=0;i

char ch=postfix.charAt(i);

if(ch>='0' && ch<='9')yAAKlrp{

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);

}

}

}

运行结果如下：

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 '/':

http:// // 当栈不空且栈顶运算符优先级高时，包括*、/

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='0' && ch<='9'){ // 获取运算的整数

postfix.append(ch); // 将数字追加到后缀表达式中

i++;

if(i

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 stack=new LinkedStack();

int value=0;

System.out.println("\n计算过程：");

for(int i=0;i

char ch=postfix.charAt(i);

if(ch>='0' && ch<='9')yAAKlrp{

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);

}

}

}

运行结果如下：

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 stack=new LinkedStack();

int value=0;

System.out.println("\n计算过程：");

for(int i=0;i

char ch=postfix.charAt(i);

if(ch>='0' && ch<='9')yAAKlrp{

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);

}

}

}

运行结果如下：

char ch=postfix.charAt(i);

if(ch>='0' && ch<='9')yAAKlrp{

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);

}

}

}

运行结果如下：

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。