`
zha_zi
  • 浏览: 593053 次
  • 性别: Icon_minigender_1
  • 来自: 西安
社区版块
存档分类
最新评论

逆波兰表达式

 
阅读更多

逆波兰表达式
 逆波兰表达式又叫做后缀表达式。在通常的表达式 中，运算符总是置于与之相关的两个运算对象之间，所以，这种表示法也称为中缀表示。波兰逻辑学家 J.Lukasiewicz于1929年提出了另一种表示表达式的方法。按此方法，每一运算符都置于其运算对象之后，故称为后缀表示。

逆波兰表达式，它的语法规定，表达式必须以逆波兰表达式的方式给出。逆波兰表达式又叫做后缀表达式。这个知识点在数据结构和编译原理这两门课程中都有介绍，下面是一些例子：
正常的表达式       逆波兰表达式 　
a+b   --->  a,b,+ 　　
a+(b-c) --->  a,b,c,-,+ 　　
a+(b-c)*d   --->  a,b,c,-,d,*,+ 　　
a+d*(b-c)     --->  a,d,b,c,-,*,+

逆波兰表达式的用途
它的优势在于只用两种简单操作，入栈和出栈就可以搞定任何普通表达式的运算。其运算方式如下： 按顺序扫描逆波兰表达式 ，如果当前字符为变量或者为数字，则压栈，如果是运算符，则将栈顶两个元
素弹出作相应运算，结果再入栈，最后当表达式扫描完后，栈里的就是结果。

中序表达式转换为逆波兰表达式
1、建立运算符栈stackOperator用于运算符的存储 ，此运算符在栈内遵循越往栈顶 优先级越高 的原则 。
2、预处理表达式，正、负号前加0(如果一个加号（减号）出现在最前面 或左括号 后面，则该加号（减号） 为正负号) 。 　　
3、顺序扫描表达式，如果当前字符是数字（优先级为0的符号），则直接输出该数字；如果当前字符为运算符或括号（优先级不为0的符号），则判断第4点 。 　　
4、若当前运算符为'('，直接入栈 ;
若为')'，出栈并顺序输出运算符直到遇到第一个'('，遇到的第一个'('出栈但不输出；
若为其它，比较stackOperator栈顶元素与当前元素的优先级：如果栈顶元素是'('， 当前元素入栈 ； 如果栈顶元素 >= 当前元素， 出栈并顺序输出 运算符直到 栈顶元素 < 当前元素，然后 当前元素入栈 ；   如果 栈顶元素 < 当前元素，直接入栈。
5、重复第3点直到表达式扫描完毕。　　
6、顺序出栈并输出运算符直到栈元素为空。

上面的算法比较抽象，下面来个实际例子 ：

写一个方法，参数传递一个字符串表达式，返回结果为表达式计算结果。
如：传递表达式"5 + ((1 + 2) * 4) − 3"返回计算的结果。
1.将中缀表达式转换为逆波兰表达式
1)建立一个运算符栈 stackOperator 用来存放运算符；建立一个字符串链表reversePolishExpression用来存放逆波兰表达式
2)顺序扫描 "5 + ((1 + 2) * 4) − 3"，根据算法可以得出 stackOperator 及reversePolishExpression值的变化过程：

扫描     操作    stackOperator值    reversePolishExpression值           注释

5           输出               空                                 5                            当前字符是数字直接输出该数字
+           入栈               +                                  5                             栈顶元素为空，不用比较，入栈
(           入栈                (                                   5                             当前运算符为'('，直接入栈
(           入栈                (  (                                5                             当前运算符为'('，直接入栈
1          输出                (  (                                5 1                          当前字符是数字直接输出该数字
+          入栈                (  ( +                             5  1                         + 优先级< 栈顶元素 ( ,入栈
2          输出                 (  ( +                             5  1  2                     当前字符是数字直接输出该数字
)           出栈                (                                   5   1  2  +                出栈并顺序输出运算符直到遇到第一个'('
*           入栈                (  *                                5   1  2  +                 * 优先级< 栈顶元素 ( ,入栈
4          输出                 (  *                                5   1  2  +  4             当前运算符为'('，直接入栈
)           输出                 空                                  5   1  2  +  4  *          出栈并顺序输出运算符直到遇到第一个'('
-            入栈                -                                    5   1  2  +  4  *          栈顶元素为空，不用比较，入栈
3          输出                  -                                    5   1  2  +  4  *  3      当前字符是数字直接输出该数字
最后     输出                 空                                  5   1  2  +  4  *  3  -   顺序出栈并输出运算符直到栈元素为空

下表给出了该逆波兰表达式从左至右求值的过程，堆栈栏给出了中间值，用于跟踪算法。

输入 操作 堆栈 注释
5 入栈 5
1 入栈 5, 1
2 入栈 5, 1, 2
+ 加法运算 5, 3 (1, 2)出栈；将结果（3）入栈
4 入栈 5, 3, 4
* 乘法运算 5, 12 (3, 4)出栈；将结果（12）入栈
+ 加法运算 17 (5, 12)出栈；将结果 (17)入栈
3 入栈 17, 3
− 减法运算 14 (17, 3)出栈；将结果（14）入栈

计算完成时，栈内只有一个操作数，这就是表达式的结果：14

转载地址：http://hi.baidu.com/johnsoncr/blog/item/99e270d35831b4d2a9ec9a03.html

 

 

 算法实现

package arithmetic.rpn;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * 逆波兰算法实现
 * @author ty93
 *
 */
public class RPN {

	public Stack<String> operatorStack = new Stack<String>();
	public Stack<String> calculateStack = new Stack<String>();
	private Map<Character, Character> mapOperator = null;

	public RPN() {
		mapOperator = new HashMap<Character, Character>();
		mapOperator.put('+', '1');
		mapOperator.put('-', '1');
		mapOperator.put('*', '2');
		mapOperator.put('/', '2');
		mapOperator.put('(', '0');
		mapOperator.put(')', '0');
		mapOperator.put('{', '0');
		mapOperator.put('}', '0');
		mapOperator.put('[', '0');
		mapOperator.put(']', '0');
	}

	public int getLevelByChar(char c) {
		return Integer.parseInt(String.valueOf(mapOperator.get(c)));
	}

	public void scanExpress(String express) {
		for (char c : express.toCharArray()) {
			if (c == ' ')
				continue;
			executeOperator(c);
		}
	}

	public void executeOperator(String s) {

	}

	@SuppressWarnings("static-access")
	public void executeOperator(Character c) {
		if (c.isDigit(c)) {
			calculateStack.add(String.valueOf(c));
		} else {
			switch (c) {
			case '(':
				operatorStack.push(String.valueOf(c));
				break;
			case ')':
				while (true) {
					String operator = operatorStack.pop();
					if (operator.equals("(")) {
						return;
					} else {
						calculateStack.push(operator);
					}
				}
			case '{':
				operatorStack.push(String.valueOf(c));
				break;
			case '}':
				while (true) {
					String operator = operatorStack.pop();
					if (operator.equals("{")) {
						return;
					} else {
						calculateStack.push(operator);
					}
				}
			case '[':
				operatorStack.push(String.valueOf(c));
				break;
			case ']':
				while (true) {
					String operator = operatorStack.pop();
					if (operator.equals("]")) {
						return;
					} else {
						calculateStack.push(operator);
					}
				}
			case '+':
				while (true) {
					if (operatorStack.isEmpty()) {
						operatorStack.push("+");
						return;
					}
					String operator = operatorStack.peek();
					if (getLevelByChar(operator.toCharArray()[0]) >= getLevelByChar('+')) {
						calculateStack.push(operatorStack.pop());
					} else {
						operatorStack.push("+");
						return;
					}
				}
			case '-':
				while (true) {
					if (operatorStack.isEmpty()) {
						operatorStack.push("-");
						return;
					}
					String operator = operatorStack.peek();
					if (getLevelByChar(operator.toCharArray()[0]) >= getLevelByChar('-')) {
						calculateStack.push(operatorStack.pop());
					} else {
						operatorStack.push("-");
						return;
					}
				}
			case '*':
				while (true) {
					if (operatorStack.isEmpty()) {
						operatorStack.push("*");
						return;
					}
					String operator = operatorStack.peek();
					if (getLevelByChar(operator.toCharArray()[0]) >= getLevelByChar('*')) {
						calculateStack.push(operatorStack.pop());
					} else {
						operatorStack.push("*");
						return;
					}
				}
			case '/':
				while (true) {
					if (operatorStack.isEmpty()) {
						operatorStack.push("/");
						return;
					}
					String operator = operatorStack.peek();
					if (getLevelByChar(operator.toCharArray()[0]) >= getLevelByChar('/')) {
						calculateStack.push(operatorStack.pop());
					} else {
						operatorStack.push("/");
						return;
					}
				}
			default:
				break;
			}
		}
	}

	public int getResult() {

		return 0;
	}

	public static void main(String[] args) {
		RPN rpn = new RPN();
		String str = "5 + ( ( 1+2)*4)−3";
		rpn.scanExpress(str);
		System.out.println(rpn.calculateStack);
	}
}

运算结果  [5, 1, 2, +, 4, *, 3]

分享到：
| ThreadPoolExecutor
评论
3 楼 zha_zi 2012-02-05  
cguang 写道
运算结果  [5, 1, 2, +, 4, *, 3]少了减号,应该是[5, 1, 2, +, 4, *, 3，-]吧
public void scanExpress(String express) {
        for (char c : express.toCharArray()) {
            if (c == ' ')
                continue;
            executeOperator(c);
        }
        if(!operatorStack.empty()) {
            String s = operatorStack.pop();
            calculateStack.push(s);
        }
    }
这样貌似可以，不知道是不是

程序没怎么优化，当时随便写的就验证了一下算法，你的应该也是可以的
2 楼 cguang 2012-01-18  
运算结果  [5, 1, 2, +, 4, *, 3]少了减号,应该是[5, 1, 2, +, 4, *, 3，-]吧
public void scanExpress(String express) {
        for (char c : express.toCharArray()) {
            if (c == ' ')
                continue;
            executeOperator(c);
        }
        if(!operatorStack.empty()) {
            String s = operatorStack.pop();
            calculateStack.push(s);
        }
    }
这样貌似可以，不知道是不是
1 楼 stin 2011-11-24  
讲的很清楚，谢谢
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    逆波兰表达式实现

    逆波兰表达式实现 逆波兰表达式是一种后缀表达式，通常用于表示数学表达式的计算顺序。它的特点是运算符在后面，先计算括号里的运算，然后计算乘除，最后计算加减。逆波兰表达式的实现可以通过栈或队列来实现。 逆...

    基于逆波兰表达式的计算程序

    逆波兰表达式，又称后缀表达式，是一种用于表示数学计算的符号表示法。它将操作符放在操作数之后，避免了使用括号，简化了运算过程。在基于逆波兰表达式的计算程序中，通常包括以下几个核心知识点： 1. **逆波兰...

    逆波兰表达式及其算法实现

    ### 逆波兰表达式及其算法实现 #### 一、引言 逆波兰表达式（Reverse Polish Notation, RPN）是一种特殊的数学表达式表示方法，它最初由波兰逻辑学家Jan Łukasiewicz提出。与传统的中缀表达式相比，逆波兰表达式...

    逆波兰表达式 c语言实现

    逆波兰表达式，又称后缀表达式，是一种在编译原理和计算机科学中常见的表示算术和逻辑表达式的方式。它的主要特点是操作符位于其操作数之后，这与我们常用的中缀表达式（操作符位于操作数之间）不同。这种表示方式在...

    转化为逆波兰表达式

    C语言：设计一个算法，将一般算术表达式转化为逆波兰表达式，并求逆波兰表达式的值。数据结构实验

    简易灰色逆波兰表达式计算器代码

    逆波兰表达式（Reverse Polish Notation，RPN）是一种没有括号且运算符放在操作数之后的数学表达式表示方式，常用于计算器设计。在这个简易的灰色逆波兰表达式计算器中，我们主要涉及以下几个关键知识点： 1. **逆...

    用二叉树存储逆波兰表达式

    逆波兰表达式是一种特殊的数学表示法，也称为后缀表达式。它将操作符放置在操作数之后，以此避免使用括号。这种表示法在计算和解析时特别有用，因为无需考虑运算符优先级，只需按照操作数出现的顺序进行计算即可。在...

    逆波兰表达式的C++实现

    逆波兰表达式，又称后缀表达式，是一种在计算领域广泛应用的数学表示方式，它将操作符放在操作数之后，避免了使用括号来明确运算优先级。这种表示方法非常适合用栈来处理，因为可以直观地按照“后进先出”（LIFO）的...

    逆波兰表达式算法_表达式_

    逆波兰表达式（Reverse Polish Notation，RPN）算法是一种基于后缀表示法的计算方法，主要用于解决数学表达式的求值问题。它将运算符放置在操作数之后，避免了括号的使用，使得表达式求值的过程更为直观。在这个算法...

    逆波兰表达式求值源代码

    逆波兰表达式求值是计算机科学中的一个重要概念，主要用于避免使用括号来表示运算优先级，从而简化表达式的解析过程。逆波兰表达式，又称后缀表达式，是一种没有括号、无需考虑运算符优先级的数学表达式书写方式。在...

    逆波兰表达式求解的程序（2种方法）

    逆波兰表达式，又称后缀表达式，是一种用于表示数学计算的符号表示法。它将操作符放在操作数之后，避免了使用括号来决定运算的优先级，从而简化了解析过程。本教程将介绍两种在C/C++或Linux环境下求解逆波兰表达式的...

    易语言源码逆波兰表达式计算易语言源码.rar

    易语言源码逆波兰表达式计算易语言源码.rar 易语言源码逆波兰表达式计算易语言源码.rar 易语言源码逆波兰表达式计算易语言源码.rar 易语言源码逆波兰表达式计算易语言源码.rar 易语言源码逆波兰表达式计算易语言...

    将一个字符串转换为其逆波兰表达式

    逆波兰表达式，又称后缀表达式，是一种不使用括号的数学表达式表示方法，它使用栈的数据结构来解析和计算表达式。在逆波兰表达式中，运算符位于其操作数之后，使得表达式的解析更为简单。本篇文章将详细讲解如何用...

    用java和逆波兰表达式写的计算器

    逆波兰表达式（Reverse Polish Notation，RPN）是一种数学表达式表示方法，它不需要使用括号，而是通过运算符后置的方式明确运算顺序。在RPN计算器中，运算符紧跟在其操作数之后，使得计算过程更为简洁。这种表示法...

    利用堆栈实现逆波兰表达式 后缀法

    ### 利用堆栈实现逆波兰表达式（后缀法） #### 一、逆波兰表达式简介 逆波兰表达式，又称后缀表达式或后缀记法，是一种没有括号且运算符位于操作数之后的数学表达式书写方式。在计算机科学中，这种表达式被广泛...

    逆波兰表达式.cpp

    逆波兰表达式的长 度不超过一行，以 "$"作为输入结束，操作数之间用空格分隔，操作符只可能有＋、—、＊、／四种 运算。例如： 23434 + 2*$。 数据结构作业

    java逆波兰表达式【栈】完整版

    【数据结构与算法】逆波兰表达式完整版，使用java语言编写。逆波兰表达式又叫做后缀表达式，是一种没有括号，并严格遵循“从左到右”运算的后缀式表达方法

Magicbox
Global site tag (gtag.js) - Google Analytics