数据结构之后缀表达式计算（链表实现）

最近熟读一本《大话数据结构》，因为在大学学过数据结构，再加上这本书通俗易懂也比较容易上手，在校期间没有用所学的东西进行实现，这次力争都实现下

上篇文章中用java实现了线性表的链式存储，链接：https://blog.csdn.net/xindanding/article/details/90373166

以下是数据结构中栈的一种体现方式，后缀表达式的计算：

public class NumberExample { //节点 private int number; private NumberExample next; public int getNumber() { return number; } public void setNumber(int number) { this.number = number; } public NumberExample getNext() { return next; } public void setNext(NumberExample next) { this.next = next; } } public class StackExample { //记录节点的链表 private NumberExample popNumber = new NumberExample(); private int length; public NumberExample pop(){ NumberExample numberExample = new NumberExample(); numberExample = popNumber; popNumber = popNumber.getNext(); length --; return numberExample; } public void push(NumberExample stu){ stu.setNext(popNumber); popNumber = stu; length++; } public NumberExample getPopStudent() { return popNumber; } public void setPopStudent(NumberExample student) { this.popNumber = student; } public int getLength() { return length; } public void setLength(int length) { this.length = length; } }

 

测试：

public static void main(String[] args) { stack(); } private static void stack(){ String str = "9,3,1,-,3,*,+,10,2,/,+"; String sign = "+-*/"; String[] exp = str.split(","); StackExample stack = new StackExample(); int result = 0; for(int i = 0; i < exp.length; i++){ if(sign.contains(exp[i])){ NumberExample numberExample1 = stack.pop(); NumberExample numberExample2 = stack.pop(); if("+".equals(exp[i])){ result = numberExample2.getNumber() + numberExample1.getNumber(); }else if("-".equals(exp[i])){ result = numberExample2.getNumber() - numberExample1.getNumber(); }else if("*".equals(exp[i])){ result = numberExample2.getNumber() * numberExample1.getNumber(); }else if("/".equals(exp[i])){ result = numberExample2.getNumber() / numberExample1.getNumber(); } NumberExample numberExample = new NumberExample(); numberExample.setNumber(result); stack.push(numberExample); //将结果result入栈 }else{ NumberExample numberExample = new NumberExample(); numberExample.setNumber(Integer.parseInt(exp[i])); stack.push(numberExample); } System.out.println(result); } }

后面会用java语言对中缀表达式转后缀表达式进行具体实现