中缀表达式(数学表达式)转后缀表达式

前言

在进行简单的四则运算时,我们所定义的数学表达式也可以称为中缀表达式。中缀表达式,名顾思意就是所有的运算符都在操作数之中,这种形式的表达方式便于我们在现实中的计算。但是在计算机中,由于计算机没有像我们人类一样拥有“充满智慧的大脑”,因此这种表达式并不适合计算机来进行处理和运算。

为了便于计算机来进行处理和运算,波兰的一位逻辑学家提出波兰式(前缀表达式),即所有的运算符都在操作数的之前。再后来又出现逆波兰式(后缀表达式),即所有的运算符都在操作数之后。这两种表达式都是利用栈来进行操作的,在计算机进行运算时非常方便和快捷。

例如:

中缀表达式:1+(2-3)*4/5

后缀表达式:123-4*5/+

算法分析

步骤一:
此次涉及的中缀式的组合方式为:操作数(0-9,可以是多位数),以及运算符加号、减号、乘号、除号和左、右括号。这里定义运算符的优先级;加号、减号运算符的优先级为1,乘号、除号运算符的优先级为2。数字越大,优先级越大。

步骤二:
定义两个栈,分别为nStack栈和oStack栈;nStack栈存放操作数和从oStack栈弹出的运算符,oStack栈存放运算符。

步骤三:
从左往右读取中缀式(如果是将中缀式转为前缀式,则是从右往左读取中缀式)。

步骤四:
当读取到操作数时,将该操作数压入nStack栈。

步骤五:
当读取到左括号时,直接压入oStack栈。

步骤六:
当读取到右小括号时,将oStack栈中的所有运算符依次弹出并压入到nStack栈中,直至遇到左括号为止并将左括号从nStackz栈中删除。

步骤七:
当读取到运算符时,如果oStack栈为空,则直接将该运算符压入到oStack栈中;如果不为空并且oStack栈的运算符是左括号时,也将该运算符压入到oStack栈中,否则就与oStack栈栈顶的运算符比较优先级。

步骤八:
如果该运算符的优先级大于oStack栈顶的运算符的优先级,则将该运算符压入oStack栈。如果该运算符的优先级小于或者等于oStack栈顶的运算符的优先级,则将当前oStack栈栈顶的运算符弹出并压入到nStack栈中;此时继续将该运算符和oStack栈栈顶的运算符进行优先级比较,之后重复步骤八。

步骤九:
继续读取中缀表达式,重复步骤三、四、五、六、七、八。

步骤十:
当遍历完中缀表达式后,将oStack栈中的运算符依次弹出并压入到nStack栈中,将nStack栈中的元素依次从栈底往栈顶输出,输出结果就是该中缀式对应的后缀式。

实现代码

import java.util.Stack;

/**
 * 中缀表达式转换后缀表达式
 *
 * @author 谈笑、
 * @dateTime 2020/9/25 21:52
 */
public class GetPostfixExpression {

	/**
	 * 为前缀表达式添加空格分隔符,后续使用空格来分割后缀表达式中的
	 * 操作数、运算符和左、右小括号。
	 *
	 * @param exp 中缀表达式(数学表达式)
	 * @return 添加了空格分隔符的前缀表达式
	 */
	public String expressionAddSpace(String exp) {

		// 存放添加空格后的中缀表达式
		StringBuilder stringBuilder = new StringBuilder();

		// 将中缀表达式转换为字符数组,实现操作数和运算符的单个读取。
		char[] chars = exp.toCharArray();

		// 循环遍历操作数和运算符
		for(int i = 0; i < chars.length; i++) {
			switch (chars[i]) {
				/* 遍历到加号、乘号、除号运算符,在其左右两边各添加一个空格作为分隔符。*/
				case '+' : { }
				case '*' : { }
				case '/' : {
					stringBuilder.append(" " + chars[i] + " ");break;
				}
				/* 遍历到减号运算符 */
				case '-' : {
					/**
					 * 因为减号涉及到负数,如果表达式的首位是减号运算符时,可以认定这个
					 * 减号与后面即将读取的操作数是一个整体,也就是说应该读取一个负数。
					 */
					if((i == 0) || (chars[i - 1] == '(')) {
						/**
						 * 将减号运算符与后面的操作数组合成一个负数,操作数不需要添加空
						 * 格(避免多位操作数被异常分割为单位操作数)。
						 */
						stringBuilder.append(chars[i] + "" + chars[i + 1]);

						// 组合完成后跳过后面的操作数,避免重复入栈。
						i += 1;break;

					} else {

						// 在减号运算符两边加上空格分隔符
						stringBuilder.append(" " + chars[i] + " ");break;
					}
				}
				/* 遍历到左括号运算符 */
				case '(' : {
					// 在其右边添加一个空格。
					stringBuilder.append(chars[i] + " ");break;
				}
				/* 遍历到右括号运算符 */
				case ')' : {
					// 右小括号,在其左边添加一个空格。
					stringBuilder.append(" " + chars[i]);break;
				}
				/* 除运算符之外的所有操作数 */
				default : {
					// 操作数不需要添加空格(避免多位操作数被异常分割为单位操作数)。
					stringBuilder.append(chars[i]);break;
				}
			}
		}
		return stringBuilder.toString();
	}


	/**
	 * 根据当前传入运算符返回该运算符的优先级;加、减运算符的优先级
	 * 为1,乘、除的优先级为2。数字越大,优先级就越大。
	 *
	 * @param operator 运算符
	 * @return 返回当前运算符的优先级
	 */
	public int getOperatorPriority(String operator) {
		if("+".equals(operator) || "-".equals(operator)) {
			// 如果是加、减运算符,则返回优先级1。
			return 1;

		} else if("*".equals(operator) || "/".equals(operator)) {

			// 如果是乘、除运算符,则返回优先级2。
			return 2;
		}
		// 否则返回0
		return 0;
	}


	/**
	 * 将运算符入栈;如果当前oStack栈为空或oStack栈栈顶的运算符为左
	 * (后缀表达式)、右(前缀表达式)小括号时,则直接将该运算符入栈,否
	 * 则比较运算符的优先级,根据优先级来进行入栈、出栈操作。
	 *
	 * @param oStack   运算符栈
	 * @param nStack   操作数栈
	 * @param operator 入栈的运算符
	 */
	public void operatorInAndOutStack(Stack<String> oStack, Stack<String> nStack, String operator) {
		if(nStack.empty()) {
			// 如果nStack栈为空时,直接将该运算符压入到nStack栈中。
			nStack.push(operator);

		} else {

			// 获取到当前nStack栈栈顶的运算符
			String nStackTopOperator = nStack.peek();

			if("(".equals(nStackTopOperator)) {
				// 如果当前nStack栈栈顶的运算符是左小括号时,直接将该运算符压入到nStack栈中。
				nStack.push(operator);

			} else {

				// 当栈顶的运算符不是左、右小括号时,则进行运算符的优先级比较操作。

				// 获取到当前nStack栈栈顶的运算符的优先级
				int nStackTopOperatorPriority = this.getOperatorPriority(nStackTopOperator);

				// 获取到当前需要压入到nStack栈中的运算符的优先级
				int thisOperatorPriority = this.getOperatorPriority(operator);

				if(thisOperatorPriority > nStackTopOperatorPriority) {

					/* 如果当前需要压入到nStack栈中的运算符的优先级比当前nStack栈栈顶的运算符
					   的优先级高,则直接将该运算符压入到nStack栈中。 */
					nStack.push(operator);

				} else {

					/* 如果当前需要压入到nStack栈中的运算符的优先级比当前nStack栈栈顶的运算符
					   的优先级相等或底时,则将当前nStack栈栈顶的一个运算符弹出并压入到oStack
					   栈中。而后,继续继续将该运算符进行递归、遍历操作。*/

					// 将当前nStack栈栈顶的一个运算符弹出并压入到oStack栈中
					oStack.push(nStack.pop());

					// 递归重复判断,直至运算符入栈。
					this.operatorInAndOutStack(oStack, nStack, operator);
				}
			}
		}
	}


	/**
	 * 将右小括号到左小括号之间的所有运算符从oStack栈依次弹出压入到nStack栈中。
	 *
	 * @param oStack 运算符栈
	 * @param nStack 操作数栈
	 */
	public void operatorOutOfStack(Stack<String> oStack, Stack<String> nStack) {
		/**
		 * 当压入到oStack栈中的运算符是右小括号时,依次弹出nStack栈中的运算符,直
		 * 至遇到左小括号时,停止弹出操作,并将左小括号从nStack栈中删除。
		 */
		if(!nStack.empty()) {
			// 将左小括号之前的所有运算符弹出并压入到oStack栈中
			while (!"(".equals(nStack.peek())) {
				oStack.push(nStack.pop());
			}
		}
		// 运算符弹出完毕后,删除左小括号。
		nStack.remove("(");
	}


	/**
	 * 通过已经分割好的中缀表达式,根据表达式中的操作数、运算符和左、右
	 * 小括号来解析并获取到后(前)表达式。
	 *
	 * @param exps 中缀表达式数组
	 * @return 存储后(中)缀表达式的栈
	 */
	public Stack<String> analyticInfixExpression(String[] exps) {
		// 定义nStack栈,存放操作数以及oStack栈中弹出的运算符。
		Stack<String> nStack = new Stack<String>();

		// 定义oStack栈,存放运算符。
		Stack<String> oStack = new Stack<String>();

		// 遍历中缀表达式数组,解析每一个操作数、运算符和左右小括号。
		for(int i = 0; i < exps.length; i++) {
			switch (exps[i]) {
				case "+" : {}
				case "-" : {}
				case "*" : {}
				case "/" : {
					// 遍历到加号、减号、乘号、除号运算符,进行运算符的优先级比较操作。
					this.operatorInAndOutStack(oStack, nStack, exps[i]);break;
				}
				case "(" : {
					// 遍历到左小括号,直接将左小括号压入到nStack栈中。
					nStack.push(exps[i]);break;
				}
				case ")" : {
					// *遍历到右小括号,依次将oStack栈中的运算符弹出并压入到nStack栈中,直至遇到左小括号为止。
					this.operatorOutOfStack(oStack, nStack);break;
				}
				default : {
					// 遍历到操作数,直接将该操作数压入oStack栈中。
					oStack.push(exps[i]);break;
				}
			}
		}

		// 将nStack栈中的所有运算符依次弹出并压入到oStack中。
		while (!nStack.empty()) {
			oStack.push(nStack.pop());
		}

		// 返回oStack栈
		return oStack;
	}


	/**
	 * 根据传递的中缀表达式和解析方式,将中缀表达式转换为前缀表达式并返回。
	 *
	 * @param exp  中缀表达式(原式)
	 * @return 转换好的前(后)缀表达式
	 */
	public String getExpression(String exp) {
		// 通过空格来分割、解析到每一个操作数和运算符。
		String[] exps = this.expressionAddSpace(exp).split(" ");

		// 获取到存放已经转换好的后缀表达式的栈,并将栈内的元素转换为字符串数组。
		String[] rStack = this.analyticInfixExpression(exps).toArray(new String[]{});

		// 存放每一个运算符和操作数
		StringBuilder result = new StringBuilder();

		/**
		 * 将rStack栈中的所有操作数和运算符输出,并存入StringBuffer中。这里的输
		 * 将栈底中的元素从下往上进行输出,不是直接出栈。
		 */
		result.append("[");

		// 添加逗号分隔符
		for(int i = 0; i < rStack.length; i++) {
			if(i != rStack.length - 1) {
				result.append(rStack[i] + ", ");

			} else {

				result.append(rStack[i]);
			}
		}

		result.append("]");

		// 返回最终转换好的后缀表达式
		return result.toString();
	}

	public static void main(String[] args) {

		GetPostfixExpression gpe = new GetPostfixExpression();
		System.out.println(gpe.getExpression("-123+45-(-67*890)/12+123"));

	}

}

相关文件

GetPostfixExpression.zip

评论

  1. TanXiao 博主
    Windows Chrome
    2月前
    2020-10-06 13:03:13

  2. 手扶式拖拉机
    Android Chrome
    2月前
    2020-10-06 13:22:41

    厉害呀

  3. TanXiao 博主
    Windows Chrome
    1月前
    2020-10-13 15:19:53

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇