首页 > 代码库 > 桟的使用之算术表达式求值
桟的使用之算术表达式求值
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()); }}这段代码为了简单起见要求输入表达式没有省略任何括号，数字和字符均以空白字符间隔：
桟的使用之算术表达式求值
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。