首页 > 代码库 > 桟的使用之算术表达式求值

桟的使用之算术表达式求值

2024-07-29 15:34:13   221人阅读

1.  背景知识

对于算术表达式（1+（（2+3）*（4+5））），如何使用程序进行计算能够很好表示运算符的优先级，从而获得正确的结果呢？简化处理，我们将算术表达式当做一个字符串，包含运算数，左括号，运算符和右括号，这里只处理带有加减乘除以及求平方根的运算。E.W.Dijkstra发明了一种简单的算法，使用两个栈，一个用于保存运算符，一个用于保存运算数，具体算法操作如下：

表达式由括号，运算符和操作数组成，依据以下4中情况从左到右将这些实体送入桟中

  • 将操作数送入操作数桟；
  • 将运算符送入运算符桟；
  • 遇到左括号忽略；
  • 遇到右括号时，弹出一个运算符，弹出所需数量的操作数，并将运算符和操作数的结果送到操作数桟中；

2.  模拟表达式计算过程

使用两个桟来模拟表达式计算，如下图所示：

3.  代码实现

开发环境：eclipse+jdk(1.7.0_45)

 

import java.util.Scanner;class Stack<Item> {	private Node first; // 栈顶元素	private int N; // 元素数量	private class Node {		Item item;		Node next;	}		public boolean isEmpty() {		return first == null;	}		public int size() {		return N;	}		public void push(Item item) {		Node oldfirst = first;		first = new Node();		first.item = item;		first.next = oldfirst;		N++;	}		public Item pop() {		Item item = first.item;		first = first.next;		N--;		return item;	}}public class Evaluate {	@SuppressWarnings("resource")	public static void main(String[] args) {		Stack<String> ops = new Stack<String>();		Stack<Double> vals = new Stack<Double>();		Scanner scanner = new Scanner(System.in);				while(scanner.hasNext()) {			String s = scanner.next();			if (s.equals("("))			{							} else if (s.equals("+")) {				ops.push(s);			} else if (s.equals("-")) {				ops.push(s);			} else if (s.equals("*")) {				ops.push(s);			} else if (s.equals("/")) {				ops.push(s);			} else if (s.equals("sqrt")) {				ops.push(s);			} else if (s.equals(")")) {				String op = ops.pop();				Double v = vals.pop();				if (op.equals("+")) {					v = vals.pop() + v;				} else if (op.equals("-")) {					v = vals.pop() - v;				} else if (op.equals("*")) {					v = vals.pop() * v;				} else if (op.equals("/")) {					v = vals.pop() / v;				} else if (op.equals("sqrt")) {					v = Math.sqrt(v);				}				vals.push(v);			} else {				vals.push(Double.parseDouble(s));			}		}		System.out.println(vals.pop());	}}

这段代码为了简单起见要求输入表达式没有省略任何括号，数字和字符均以空白字符间隔：

桟的使用之算术表达式求值


联系
我们