正文
java数据结构代码实现,数据结构 java版
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
表达式求值 数据结构 java实现
1. 定义优先级和优先级表
Java代码
/**
* 运算符优先权
*/
public enum Precede {
/**
* 优先权高
*/
LARGER,
/**
* 优先权低
*/
LESS;
/**
* 优先级表
* + - * /
* +
* -
* *
* /
*/
private static Precede[][] precedes = new Precede[4][4];
static {
// 根据优先级表初始化precedes数组
for (int i = 0; i precedes.length; i++) {
for (int j = 0; j precedes[i].length; j++) {
if ((i == 0 || i == 1) j 1) {
precedes[i][j] = LESS;
} else {
precedes[i][j] = LARGER;
}
}
}
}
/**
* 判断2个运算符的优先级
*/
public static Precede judgePrecede(char operand1, char operand2) {
int left = getIndex(operand1);
int right = getIndex(operand2);
return precedes[left][right];
}
/**
* 获取运算符对应的数组索引
*/
private static int getIndex(char operand) {
switch (operand) {
case '+':
return 0;
case '-':
return 1;
case '*':
return 2;
case '/':
return 3;
default:
throw new IllegalArgumentException();
}
}
}
2. 表达式求值
Java代码
/**
* 整数表达式运算
*/
public class EvaluateExpression {
/**
* 表达式
*/
private String expression;
/**
* 最初的表达式
*/
private String initExpression;
/**
* 运算符栈
*/
private MyStackCharacter optr = new MyArrayStackCharacter();
/**
* 操作数栈
*/
private MyStackInteger opnd = new MyArrayStackInteger();
/**
* 表明下一个是否应该是数字
*/
private boolean numberNext;
public EvaluateExpression(String expression) {
this.expression = expression;
this.initExpression = expression;
numberNext = true;
}
/**
* 求值
*/
public Integer evaluate() {
delBlank();
handleParentheses();
while (true) {
if ("".equals(expression)) {
break;
}
if (expression.matches("^-?\\d+.*$") numberNext) {
opnd.push(getInteger());
continue;
} else {
Character operand = expression.charAt(0);
numberNext = true;
expression = expression.substring(1);
Character pop = optr.pop();
if (pop == null) {
optr.push(operand);
continue;
} else {
Precede precede = Precede.judgePrecede(pop, operand);
switch (precede) {
// 优先级高时运算前2个操作数
case LARGER: {
optr.push(operand);
Integer next = opnd.pop();
Integer last = opnd.pop();
evaluateNow(last, pop, next);
break;
}
// 优先级低时运算前一个操作数和后一个操作数
case LESS: {
optr.push(pop);
Integer last = opnd.pop();
Integer next = getInteger();
evaluateNow(last, operand, next);
break;
}
}
}
}
}
// 运算结果
Integer result = null;
if (optr.length() == 0 opnd.length() == 1) {
result = opnd.pop();
} else if (optr.length() == 1 opnd.length() == 2) {
Integer next = opnd.pop();
Integer last = opnd.pop();
evaluateNow(last, optr.pop(), next);
result = opnd.pop();
} else {
throw new RuntimeException();
}
return result;
}
/**
* 进行实际的运算，并将结果入栈
*/
private void evaluateNow(Integer last, Character operand, Integer next) {
switch (operand) {
case '+':
opnd.push(last + next);
break;
case '-':
opnd.push(last - next);
break;
case '*':
opnd.push(last * next);
break;
case '/':
opnd.push(last / next);
break;
}
}
/**
* 获得表达式开头部分的整数
*/
private Integer getInteger() {
StringBuilder sb = new StringBuilder();
int count = 0; // 整数位
boolean lessZero = false; // 是否是负数
if (expression.startsWith("-")) {
sb.append("-");
count++;
lessZero = true;
}
int i = (lessZero ? 1 : 0);
for (; i expression.length(); i++) {
char c = expression.charAt(i);
if (c = '0' c = '9') {
sb.append(c);
count++;
} else {
break;
}
}
expression = expression.substring(count);
numberNext = false;
return Integer.valueOf(sb.toString());
}
/**
* 处理括号. 将括号内的字符串作为子表达式计算.
*/
private void handleParentheses() {
while (expression.contains("(")) {
// 左括号的索引
int left = 0;
// 右括号的索引
int right = 0;
// 左括号的数量
int count = 0;
// 求出左括号索引
left = expression.indexOf('(');
// 求出对应的右括号索引
for (int i = left; i expression.length(); i++) {
char c = expression.charAt(i);
if (c == ')') {
count--;
// count为0时才是对应的右括号
if (count == 0) {
right = i;
break;
}
} else if (c == '(') {
count++;
} else {
continue;
}
}
// 左右括号之间是一个子表达式, 计算子表达式的值，并根据结果构造出新的表达式
EvaluateExpression evaluateExpression = new EvaluateExpression(expression.substring(left + 1, right));
expression = expression.substring(0, left) + evaluateExpression.evaluate()
+ expression.substring(right + 1);
}
}
/**
* 删除表达式中的空白字符
*/
private void delBlank() {
expression = expression.replaceAll("\\s", "");
}
@Override
public String toString() {
return initExpression;
}
}
3. 进行测试
Java代码
@Test
public void testEvaluate() {
EvaluateExpression expression = new EvaluateExpression("1 + 2 ");
System.out.println(expression + " = " + expression.evaluate());
expression = new EvaluateExpression("4 + 2 * 3 - 10 / 5");
System.out.println(expression + " = " + expression.evaluate());
expression = new EvaluateExpression("(1+2) * (4 + 5) - (9 / 7)");
System.out.println(expression + " = " + expression.evaluate());
expression = new EvaluateExpression("(1 + (3 * (4 - 9)))");
System.out.println(expression + " = " + expression.evaluate());
expression = new EvaluateExpression("(1 + (3 * (4 - 9))) + (3 * (2 + 3))");
System.out.println(expression + " = " + expression.evaluate());
}
测试的结果为:
1 + 2 = 3
4 + 2 * 3 - 10 / 5 = 8
(1+2) * (4 + 5) - (9 / 7) = 26
(1 + (3 * (4 - 9))) = -14
(1 + (3 * (4 - 9))) + (3 * (2 + 3)) = 1
相关问答
Q1: 用java实现一个数据结构！
import java.io.IOException;
import java.util.Scanner;
public class LinkList {
private static Scanner san = new Scanner(System.in);
public static void main(String[] args) throws IOException {
List list = new List();
for (int i = 1; i = 10; i++) {
System.out.print("请输入第" + i + "个数: ");
list.add(san.nextInt());
list.print();
}
System.out.println("输入的数据如下: ");
list.print();
}
}
class node {
int data;
node next = this; // 指向自己
}
class List {
private node header = new node();
// 循环链表的尾部添加数据
public node add(int data) {
node current = new node();
node temp = header;
while (temp.next != header)
temp = temp.next;
current.data = data;
current.next = temp.next;
temp.next = current;
return current;
}
// 查询某个数字的位置 如果不在 返回-1；
public int search(int data) {
node temp = header;
int n = 0;
while (temp.next != header) {
temp = temp.next;
n++;
if (temp.data == data)
break;
}
if (temp.data == data)
return n;
else
return -1;
}
// 打印出整个链表
public void print() {
node temp = header;
while (temp.next != header) {
temp = temp.next;
System.out.print(temp.data + " ");
}
System.out.println();
}
// 插入数据
public node Insert(int pos, int data) {
node temp = header;
node current = new node();
for (int i = 0; i pos - 1; i++) {
if (temp.next != header) {
temp = temp.next;
} else
return null;
}
current.data = data;
if (temp.next != header) {
current.next = temp.next;
}
temp.next = current;
return current;
}
// 删除某个数据
public node del(int data) {
node temp = header;
node oldtemp = null;
node current = null;
while (temp.next != header) {
oldtemp = temp;
temp = temp.next;
if (temp.data == data) {
current = temp;
break;
}
}
if (current == header)
return null;
oldtemp.next = current.next;
return current;
}
}
Q2: 用Java语言编写数据结构中顺序表的插入删除查找代码并实现
public class Test {
public static void main(String[] args) {
int length = 5;
int ai = 1;
String data = "data";
String[] array = insertArrar(data, ai, length);
data = delArray(array, ai, length);
System.out.println(data);
}
public static String[] insertArrar(String data,int ai,int length){
String[] array = new String[length];
array[ai] = data;
return array;
}
public static String delArray(String[] array,int ai,int length){
String data = "";
data=array[ai];
array[ai]=null;
for(int i = 0; iarray.length;i++){
System.out.println(array[i]);
}
return data;
}
}
Q3: 数据结构在java里如何实现?
首先Java没有指针(为了安全和方便编程).
其次数据结构和指针无关，和语言也无关.
Java封装好了各种基本的数据结构 比如:
数组,队列,Stack,HashTable,HashSet,HaspMap等等
你说的顺序表 Java中你可以用:
ArrayList 这个类:
例子:
如果你自己想用Java裸写一个类似功能的类可以参考这个:
