//中置表达式转为后置表达式的java的代码(可实现括号的计算)(内含大量函数好好分析)
//经典例题分析和理解，在算法与数据结构的这堂课上
import java.util.*;
import java.util.stream.Collectors;
public class InfixtoSuffix {
/**
*提前将 符号的优先级定义好
*/
private static final Map<Character, Integer> basic = new HashMap<Character, Integer>();
static {
basic.put('-', 1);
basic.put('+', 1);
basic.put('*', 2);
basic.put('/', 2);
basic.put('(', 0);//在运算中 （）的优先级最高，但是此处因程序中需要 故设置为0
}
/**
* 将 中缀表达式 转化为 后缀表达式
*/
public static String toSuffix(String infix){
List<String> queue = new ArrayList<String>();//定义队列 用于存储 数字 以及最后的 后缀表达式
List<Character> stack = new ArrayList<Character>();//定义栈 用于存储 运算符 最后stack中会被 弹空
char[] charArr = infix.trim().toCharArray();//字符数组， 用于拆分数字或符号 trim可以去掉首尾的空白符 tocharArray()可以将string转化为字符数组
String standard = "*/+-()";//判定标准 将表达式中会出现的运算符写出来
char ch = '&';//在循环中用来保存 字符数组的当前循环变量的 这里仅仅是初始化一个值 没有意义
int len = 0;//用于记录字符长度，非空格的所有字符长 【例如100*2,则记录的len为3 到时候截取字符串的前三位就是数字】
for (int i = 0; i < charArr.length; i++) { //开始迭代
ch = charArr[i];//保存当前迭代变量
if(Character.isDigit(ch)) {//如果当前变量为 数字
len++;
}else if(Character.isLetter(ch)) {//如果当前变量为 字母
len++;
}else if(ch == '.'){//如果当前变量为 . 会出现在小数里面
len++;
}else if(Character.isSpaceChar(ch)) {//如果当前变量为 空格 ('\n' ' ' '\t') 支持表达式中有空格出现
if(len > 0) { //若为空格 代表 一段结束 ，就可以往队列中 存入了 【例如100 * 2 100后面有空格 就可以将空格之前的存入队列了】
queue.add(String.valueOf(Arrays.copyOfRange(charArr, i - len, i)));//往 队列存入 截取的 字符串 Arrays.copyOfRange(T[] original,int from,int to) string.valueof(char[]] data)
len = 0;//长度置空
}
continue;//如果空格出现，则一段结束 跳出本次循环
}else if(standard.indexOf(ch) != -1) {//如果是上面标准中的 任意一个符号 int indexOf(char ch,int fromindex)
if(len > 0) {//长度也有
queue.add(String.valueOf(Arrays.copyOfRange(charArr, i - len, i)));//说明符号之前的可以截取下来做数字
len = 0;//长度置空
}
if(ch == '(') { //如果是左括号
stack.add(ch); //将左括号 放入栈中
continue; //跳出本次循环 继续找下一个位置
}
if (!stack.isEmpty()) {//如果栈不为empty
int size = stack.size() - 1;//获取栈的大小-1 即代表栈最后一个元素的下标
boolean flag = false;//设置标志位
while (size >= 0 && ch == ')' && stack.get(size) != '(') {//若当前ch为右括号，则 栈里元素从栈顶一直弹出，直到弹出到 左括号
queue.add(String.valueOf(stack.remove(size)));//注意此处条件：ch并未入栈，所以并未插入队列中；同样直到找到左括号的时候，循环结束了，所以左括号也不会放入队列中【也就是：后缀表达式中不会出现括号】
size--; //size-- 保证下标永远在栈最后一个元素【栈中概念：指针永远指在栈顶元素】
flag = true;//设置标志位为true 表明一直在取（）中的元素
}
while (size >= 0 && !flag && basic.get(stack.get(size)) >= basic.get(ch)) {//若取得不是（）内的元素，并且当前栈顶元素的优先级>=对比元素那就出栈插入队列，相当于先算
queue.add(String.valueOf(stack.remove(size))); //同样此处也是remove()方法，既能得到要获取的元素，也能将栈中元素移除掉
size--;
}
}
if(ch != ')') {//若当前元素不是右括号
stack.add(ch); //就要保证这个符号 入栈
} else { //否则就要出栈 栈内符号
stack.remove(stack.size() - 1);
}
}
if(i == charArr.length - 1) {//如果已经走到了 中缀表达式的最后一位
if(len > 0) {//如果len>0 就截取数字
queue.add(String.valueOf(Arrays.copyOfRange(charArr, i - len+1, i+1)));
}
int size = stack.size() - 1;//size表示栈内最后一个元素下标
while (size >= 0) {//一直将栈内 符号全部出栈 并且加入队列中【最终的后缀表达式是存放在队列中的，而栈内最后会被弹空】
queue.add(String.valueOf(stack.remove(size)));
size--;
}
}
}
return queue.stream().collect(Collectors.joining(","));//将队列中元素以,分割 返回字符串 collector可以list元素转化为collector实例，list的stream可以将list元素转化为string元素
}
public static String dealEquation(String equation){
String [] arr = equation.split(",");//根据, 拆分字符串,split(char ch,int limit),limit限制份数
List<String> list = new ArrayList<String>();//用于计算时 存储运算过程的集合【例如list中当前放置 100 20 5 / 则取出20/5 最终将结果4存入list 此时list中结果为 100 4 】
for (int i = 0; i < arr.length; i++) { //此处就是上面说的运算过程， 因为list.remove的缘故，所以取出最后一个数个最后两个数 都是size-2
int size = list.size();
switch (arr[i]) {//Double.parseDouble可以将string类型的转化为double类型
case "+": double a = Double.parseDouble(list.remove(size-2))+ Double.parseDouble(list.remove(size-2)); list.add(String.valueOf(a)); break;
case "-": double b = Double.parseDouble(list.remove(size-2))- Double.parseDouble(list.remove(size-2)); list.add(String.valueOf(b)); break;
case "*": double c = Double.parseDouble(list.remove(size-2))* Double.parseDouble(list.remove(size-2)); list.add(String.valueOf(c)); break;
case "/": double d = Double.parseDouble(list.remove(size-2))/ Double.parseDouble(list.remove(size-2)); list.add(String.valueOf(d)); break;
default: list.add(arr[i]); break;//如果是数字 直接放进list中
}
}
return list.size() == 1 ? list.get(0) : "运算失败" ; //最终list中仅有一个结果，否则就是算错了
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String b = scanner.nextLine();
String a = toSuffix(b);//传入 一串 算数公式
System.out.println(a);
System.out.println(dealEquation(a));
}
}
//通过后缀表达式来实现前缀表示式和中缀表达式的转换，这里实现不了有括号的实现
import java.util.Scanner;
import java.util.Stack;
class Node{
char val;
Node left;
Node right;
public Node(char val){
this.val=val;
}
}
public class Main {
public static Node buildTree(String str){
Stack<Node> stack=new Stack<Node>();
for(char c:str.toCharArray()){//string的数据通过toCharArray()方法实现遍历
if(c=='+'||c=='-'||c=='*'||c=='/'){
Node node=new Node(c);
Node right=stack.pop();
Node left=stack.pop();
node.left=left;
node.right=right;
stack.push(node);
}else{
Node node=new Node(c);
stack.push(node);
}
}
Node root=stack.pop();
return root;
}
public static void preOrder(Node node){//前置表达式
if(node==null)
return;
System.out.print(node.val);
preOrder(node.left);
preOrder(node.right);
}
public static void inOrder(Node node){//中置表达式
if(node==null)
return;
inOrder(node.left);
System.out.print(node.val);
inOrder(node.right);
}
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
while(scanner.hasNext()){
String str=scanner.nextLine();
Node root=buildTree(str);
preOrder(root);//从子节点开始
System.out.println();
inOrder(root);
System.out.println();
}
scanner.close();
}
}
更新于2021,10,28
