欢迎关注大数据技术架构与案例微信公众号:过往记忆大数据
过往记忆博客公众号iteblog_hadoop
欢迎关注微信公众号:
过往记忆大数据

中缀表达式转成后缀表达式实现

后缀表达式又叫做逆波兰表达式。在通常的表达式中,二元运算符总是置于与之相关的两个运算对象之间,所以,这种表示法也称为中缀表示。波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示表达式的方法。按此方法,每一运算符都置于其运算对象之后,故称为后缀表示。
运用后缀表达式进行计算的具体做法:
建立一个栈S 。从左到右读后缀表达式,如果读到操作数就将它压入栈S中,如果读到n元运算符(即需要参数个数为n的运算符)则取出由栈顶向下的n项按操作符运算,再将运算的结果代替原栈顶的n项,压入栈S中 。如果后缀表达式未读完,则重复上面过程,最后输出栈顶的数值则为结束。

计算机实现转换:

将中缀表达式转换为后缀表达式的算法思想:

  1. 开始扫描;
  2. 数字时,加入后缀表达式;
  3. 运算符:
    a.若为最高级的运算符,入栈;
    b. 若为 '(',入栈;
    c. 若为 ')',则依次把栈中的的运算符加入后缀表达式中,直到出现'(',从栈中删除'(' ;
    d. 若为不是最高级的运算符,则将从栈顶到第一个优先级不大于(小于,低于或等于)它的运算符(或 '(',但优先满足前一个条件)之间的运算符加入后缀表达式中,该运算符再入栈;

代码实现:

package com.wyp;

import java.util.Stack;

public class TestStack {

	private String testString = null;
	private Stack<Character> stack = null;

	/**
	 * @author 397090770
	 * blog: 
	 * 转载请注明来源
	 * */
	public TestStack(String testString) {
		this.testString = testString;
		this.stack = new Stack<Character>();
	}

	private void analysisString() {
		for (int i = 0; i < testString.length(); i++) {
			char c = testString.charAt(i);
			if (c == '+' || c == '-') {
				if (stack.isEmpty() || stack.peek() == '(') {
					stack.push(c);
				} else {
					while (!stack.isEmpty()
							&& (stack.peek() == '*' 
							|| stack.peek() == '/'
							|| stack.peek() == '+'
							|| stack.peek() == '-')) {
						System.out.print(stack.pop());
					}
					stack.push(c);
				}
			} else if (c == '*' || c == '/') {
				if (stack.isEmpty()
						|| stack.peek() == '+'
						|| stack.peek() == '-' 
						|| stack.peek() == '(') {
					stack.push(c);
				} else {
					while (!stack.isEmpty()
						&& (stack.peek() == '/' 
						|| stack.peek() == '*')) {
						System.out.print(stack.pop());
					}
					stack.push(c);
				}
			} else if (c == '(') {
				stack.push(c);
			} else if (c == ')') {
				char temp = ' ';
				while ((temp = stack.pop()) != '(') {
					System.out.print(temp);
				}
			} else {
				System.out.print(c);
			}
		}
		if (!stack.isEmpty()) {
			while (!stack.isEmpty()) {
				System.out.print(stack.pop());
			}
		}
	}

	public static void main(String[] args) {
		TestStack testStacknew = new TestStack("A+B*(C-D)/E+F/H");
		testStacknew.analysisString();
	}

}

运行结果:ABCD-*E/+FH/+

本博客文章除特别声明,全部都是原创!
原创文章版权归过往记忆大数据(过往记忆)所有,未经许可不得转载。
本文链接: 【中缀表达式转成后缀表达式实现】(https://www.iteblog.com/archives/161.html)
喜欢 (0)
分享 (0)
发表我的评论
取消评论

表情
本博客评论系统带有自动识别垃圾评论功能,请写一些有意义的评论,谢谢!