欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Java用栈实现 中缀表达式转后缀表达式

程序员文章站 2022-05-26 12:01:32
...

先了解一下什么是中缀和后缀表达式

中缀表达式就是我们平常写的算式,比如2*(3+4)-8/2,它对应的后缀表达式是234+*82/-。不要着急,接下来我们看看是怎么得到后缀表达式的。

当遇到数字时,直接输出,遇到符号入栈,在入栈之前需要判断各操作符的优先级大小,判断规则如下。

===栈外>栈内: 将栈外操作符入栈

===栈外<栈内: 将栈内操作符出栈

===栈内=栈外: 规定栈内高于栈外,将栈内的出栈

===遇到 ‘(’    :  直接入栈 ,入栈后将其优先级变为最低(即栈外‘(’最高,栈内‘(’最低

           遇到 ‘)’:      出栈所有操作符直达遇到 ‘(’ (栈外右括号优先级最低,低到和栈内左括号优先级相等)

具体执行如下图:(图有些粗糙)

Java用栈实现 中缀表达式转后缀表达式

接下来用Java实现一下中缀表达式转后缀表达式


public class Constant {//规定了各运算符的优先级,数值越小优先级越高
	/**
	 * 表示加法
	 */
	public static final int OPERATORS_PRIO_PLUS_IN = 4;  //栈内加法
	public static final int OPERATORS_PRIO_SUB_IN  =  4;   //栈内减法
	public static final int  OPERATORS_PRIO_MULTY_IN  =  2; //栈内乘法
	public static final int OPERATORS_PRIO_DIV_IN  =  2 ;  //栈内除法
	public static final int OPERATORS_PRIO_LEFT_BRAK_IN  =  10;  //栈内左括号

	public static final int OPERATORS_PRIO_PLUS_OUT  =  5 ; //栈外加法
	public static final int OPERATORS_PRIO_SUB_OUT  =   5;   //栈外减法
	public static final int OPERATORS_PRIO_MULTY_OUT  =  3; //栈外乘法
	public static final int OPERATORS_PRIO_DIV_OUT  =  3;   //栈外除法
	public static final int OPERATORS_PRIO_LEFT_BRAK_OUT =  1;  //栈外左括号
	public static final int OPERATORS_PRIO_RIGHT_BRAK_OUT =  10;  //栈外右括号
	public static final int OPERATORS_PRIO_ERROR = -1;
}
public class TestM1 {
	public static int Get_Prio(char opera,boolean instack)//opera是操作符,instack表示是否在栈内
	{
		int prio = Constant.OPERATORS_PRIO_ERROR;
		if(instack)//在栈内
		{
			switch(opera)
			{
			case '+':
				prio = Constant.OPERATORS_PRIO_PLUS_IN;
				break;
			case '-':
				prio = Constant.OPERATORS_PRIO_SUB_IN;
				break;
			case '*':
				prio = Constant.OPERATORS_PRIO_MULTY_IN;
				break;
			case '/':
				prio = Constant.OPERATORS_PRIO_DIV_IN;
				break;
			case '(':
				prio = Constant.OPERATORS_PRIO_LEFT_BRAK_IN;
				break;
			default:
				prio = Constant.OPERATORS_PRIO_ERROR;
				break;
			}
		}
		else//在栈外
		{
			switch(opera)
			{
			case '+':
				prio = Constant.OPERATORS_PRIO_PLUS_OUT;
				break;
			case '-':
				prio = Constant.OPERATORS_PRIO_SUB_OUT;
				break;
			case '*':
				prio = Constant.OPERATORS_PRIO_MULTY_OUT;
				break;
			case '/':
				prio = Constant.OPERATORS_PRIO_DIV_OUT;
				break;
			case '(':
				prio = Constant.OPERATORS_PRIO_LEFT_BRAK_OUT;
				break;
			case ')':
				prio = Constant.OPERATORS_PRIO_RIGHT_BRAK_OUT;
				break;
			default:
				prio = Constant.OPERATORS_PRIO_ERROR;
				break;
			}
		}
		return prio;
	}
	public static void strMidTolast(String strMid,char[] strLast){//前一个是中缀,后一个是后缀
		char[] stack = new char[strMid.length()];
		int top = 0;
		int len = strMid.length();//中缀表达式的长度
		int i = 0;//计数
		int j = 0;//strLast的下标
		int prioIn;//栈内优先级
		int prioOut;//栈外优先级 
		while(i != len){
			//判断当前的字符是不是数字,如果是数字直接入栈
			if(Character.isDigit(strMid.charAt(i))){//charAt是Stirng类型里的方法
				strLast[j++] = strMid.charAt(i);//将当前字符写入后缀表达式
				i++;
			}else{
				if(top == 0){//如果栈内没有操作符,让当前操作符入栈
					stack[top++] = strMid.charAt(i);
				}else{
					prioIn = Get_Prio(stack[top - 1],true);//得到栈顶元素的优先级
					prioOut = Get_Prio(strMid.charAt(i),false);//得到栈外元素的优先级
					if(prioIn < prioOut){//栈内优先级高,出栈
						strLast[j++] = stack[--top];
					}else if(prioIn == prioOut){//左括号右括号相遇
						top--;//出栈
						i++;
					}else{//栈外优先级高于栈内
						stack[top++] = strMid.charAt(i);
					}
				}
			}
		}
		//判断栈内是否还有运算符
		while(top > 0){
			strLast[j++] = stack[--top];
		}
	}