中缀表达式转后缀表达式

体步骤如下:

1)初始化两个栈:运算符栈s1和储存中间结果的栈s2;
2)从左至右扫描中缀表达式;
3)遇到操作数时,将其压s2;
4)遇到运算符时,比较其与s1栈顶运算符的优先级:
             (1)如果s1为空,或栈顶运算符为左括号“(”,则直接将此运算符入栈;
             (2)否则,若优先级比栈顶运算符的高,也将运算符压入s1;
             (3)否则,将s1栈顶的运算符弹出并压入到s2中,再次转到(4-1)与s1中新的栈顶运算符相比较;
5)遇到括号时:
              (1) 如果是左括号“(”,则直接压入s1
              (2) 如果是右括号“)”,则依次弹出s1栈顶的运算符,并压入s2,直到遇到左括号为止,此时将这一对括号丢弃
6)重复步骤2至5,直到表达式的最右边
7)将s1中剩余的运算符依次弹出并压入s2
8)依次弹出s2中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式

中缀表1+((2+3)×4)-5”为后缀表达式的

扫描到的元素

s2(栈底->栈顶)

s1 (栈底->栈顶)

说明

1

1

数字,直接入栈

+

1

+

s1为空,运算符直接入栈

(

1

+ (

左括号,直接入栈

(

1

+ ( (

同上

2

1 2

+ ( (

数字

+

1 2

+ ( ( +

s1栈顶为左括号,运算符直接入栈

3

1 2 3

+ ( ( +

数字

)

1 2 3 +

+ (

右括号,弹出运算符直至遇到左括号

×

1 2 3 +

+ ( ×

s1栈顶为左括号,运算符直接入栈

4

1 2 3 + 4

+ ( ×

数字

)

1 2 3 + 4 ×

+

右括号,弹出运算符直至遇到左括号

-

1 2 3 + 4 × +

-

-与+优先级相同,因此弹出+,再压入-

5

1 2 3 + 4 × + 5

-

数字

到达最右端

1 2 3 + 4 × + 5 -

s1中剩余的运算符

结果"1 2 3 + 4 × + 5 –"

package com.wang;

import java.util.*;

public class Test {

	public static void main(String[] args) {
		
		//中缀表达式
		String exp="1+((2+3)*4)-5";
		List<String> inlist=toExp(exp);
		System.out.println("中缀表达式: "+inlist);
		//对应的后缀表达式
		List<String> parseList = parseList(inlist);
		System.out.println("对应的后缀表达式: "+parseList);
		
		
		/*String Poland="3 4 + 5 * 6 -";
		//先将表达式存入Arralist,遍历Arralist配合栈完成计算
		List<String> getlist = getlist(Poland);
		System.out.println(getlist);*/
		int res=compute(parseList);
		System.out.println("结果: "+res);
	}
	
	
	public static List<String> getlist(String Poland) {
		//按空格分割字符串并存入数组
		String[] split = Poland.split(" ");
		ArrayList<String> arrayList = new ArrayList<String>();
		
		//遍历数组存入集合
		for (String i :split) {
			arrayList.add(i);
		}
		return arrayList;
	}
	
	
	public static int compute(List<String> list) {
		Stack<String> stack=new Stack<String>();
		for (String i : list) {
			//使用正则表达式取出多位数字
			if (i.matches("\\d+")) {
				//入栈
				stack.push(i);
			}else {
				//取出两个运算后入栈
				int num2=Integer.parseInt(stack.pop());
				int num1=Integer.parseInt(stack.pop());
				int res=0;
				if(i.equals("+")) {
					res=num1+num2;
				}else if (i.equals("-")) {
					res=num1-num2;
				}else if (i.equals("*")) {
					res=num1*num2;
				}
				else if (i.equals("/")) {
					res=num1/num2;
				}
				stack.push(res+"");
			}
		}
		return Integer.parseInt(stack.pop());
	}
	
	
	
	//将中缀表达式存入集合 也就是转成1,+,(,(,2,+,3,),*,4,),-,5
	public static List<String> toExp(String s){
		ArrayList<String> ls = new ArrayList<String>();
		//用于遍历中缀字符串
		int i=0;
		//用于拼接多位数
		String str;
		//每遍历一位就放进c里
		char c;
		do {
			//如果它是一个字符就加入ls
			if((c=s.charAt(i))<48||(c=s.charAt(i))>59) {
				ls.add(""+c);
				i++;
			}else {
				//如果是一个数,则需要考虑是否多位数
				
				//每次拼接前重置str
				str="";
				while (i<s.length()&&(c=s.charAt(i))>=48&&(c=s.charAt(i))<=59) {
					str+=c;
					i++;
				}
				ls.add(str);
			}
		} while (i<s.length());
		return ls;
	}
	
	
	//将得到的中缀表达式分成两部分
	//存入符号栈和中间结果栈
	public static List<String> parseList(List<String> ls){
		//符号栈
		Stack<String> s1 = new Stack<String>();
		//中间结果栈
		ArrayList<String> s2 = new ArrayList<String>();
		
		for (String s : ls) {
			//如果是一个数就加入ls1
			if (s.matches("\\d+")) {
				s2.add(s);
			}else if (s.equals("(")) {
				s1.push(s);
			}else if (s.equals(")")) {
				//如果是右括号则依次弹出s1栈顶的运算符,压入s2,直到遇到左括号为止
				while (!s1.peek().equals("(")) {
					s2.add(s1.pop());
				}
				//将括号弹出消除
				s1.pop();
			}else {
				while(s1.size()!=0&&Oper.getv(s1.peek())>=Oper.getv(s)) {
					s2.add(s1.pop());
				}
				s1.push(s);
			}
		}
		
		//将s1中剩余的运算符依次弹出并加入s2
		while(s1.size() != 0 ) {
			s2.add(s1.pop());
		}
		return s2;
	}
	
}
class Oper{
	private static int ADD=1;
	private static int SUB=1;
	private static int MUL=1;
	private static int DIV=1;
	
	public static int getv(String oper) {
		int su=0;
		switch (oper) {
		case "+":
			su=ADD;
			break;
		case "-":
			su=SUB;
			break;
		case "*":
			su=MUL;
			break;
		case "/":
			su=DIV;
			break;
		}
		return su;
	}
}

上一篇:CSP-J 2021 考试总结 & 题解


下一篇:【无标题】