import java.util.ArrayList;
import java.util.Stack;
public class PostfixExp {
public static void main(String[] args) {
PostfixExp pExp = new PostfixExp();
//String exp = "a + b*c + (d * e + f) * g";
//string exp = "1+1+3*2*3-4";
//string exp = "2+(1+3)*2*3-4";
//string exp = "2+1+3*2*(3-4)";
String exp = "(13+10/2)*21*(39-4)";
String case1 = "(13+10/2)*(21*(39-4)+(13+10/2)*21*(39-4))";
String case2 = "(6*7+9+8/2*12+12/3)+88/11";
String case3 = "(6*7+9+8/2*12+12/3)+(88/11+(13+10/2)*(21*(39-4)+(13+10/2)*21*(39-4)))";
String case4 = "(6*7+9+8/2*12+12/3)+((88/11+(13+10/2)*(21*(39-4)+(13+10/2)*21*(39-4)))+(6*7+9+8/2*12+12/3)+(88/11+(13+10/2)*(21*(39-4)+(13+10/2)*21*(39-4))))";
String case5 = "(6*7+9+8/2*12+12/3)+((88/11+(13+10/2)*(21*(39-4)+(13+10/2)*21*(39-4)))+(6*7+9+8/2*12+12/3)+(88/11+(13+10/2)*(21*(39-4)+(13+10/2)*21*(39-4))))+(6*7+9+8/2*12+12/3)+((88/11+(13+10/2)*(21*(39-4)+(13+10/2)*21*(39-4)))+(6*7+9+8/2*12+12/3)+(88/11+(13+10/2)*(21*(39-4)+(13+10/2)*21*(39-4))))";
String case6 = "(3*(4+9)+8/(2*12)+12/3)+(((7+(13+10/2))*(21*(39-4)+(13+10/2)*21*(39-4)))+(6*7+9+8/2*12+12/3)+(88/11+(13+10/2)*(21*(39-4)+(13+10/2)*21*(39-4))))+(6*7+9+8/2*12+12/3)+((88/11+(13+10/2)*(21*(39-4)+(13+10/2)*21*(39-4)))+(6*7+9+8/2*12+12/3)+(88/11+(13+10/2)*(21*(39-4)+(13+10/2)*21*(39-4))))";
ArrayList<String> expList = pExp.change2PostfixExp(case6);
for(String item : expList) {
System.out.print(item + " ");
}
System.out.println("\n");
System.out.println("My answer is \t\t" + pExp.calculate(expList));
int rightAnswer = (3*(4+9)+8/(2*12)+12/3)+(((7+(13+10/2))*(21*(39-4)+(13+10/2)*21*(39-4)))+(6*7+9+8/2*12+12/3)+(88/11+(13+10/2)*(21*(39-4)+(13+10/2)*21*(39-4))))+(6*7+9+8/2*12+12/3)+((88/11+(13+10/2)*(21*(39-4)+(13+10/2)*21*(39-4)))+(6*7+9+8/2*12+12/3)+(88/11+(13+10/2)*(21*(39-4)+(13+10/2)*21*(39-4))));
System.out.println("The right answer is \t" + rightAnswer);
System.out.println();
}
private Stack<String> opStack;
private Stack<String> expStack;
private String[] ops = {"+", "-", "*", "/", "(", ")", "#"};
public PostfixExp() {
opStack = new Stack<String>();
expStack = new Stack<String>();
}
private boolean isOp(char c) {
String cStr = Character.toString(c);
for (String op : ops) {
if(cStr.equals(op)) {
return true;
}
}
return false;
}
private boolean isOp(String str) {
for(String op : ops) {
if(str.equals(op)) {
return true;
}
}
return false;
}
private int getOpPriority(String op){
if("+".equals(op) || "-".equals(op)) {
return 1;
}
else if("*".equals(op) || "/".equals(op)) {
return 2;
}
else if("(".equals(op)) {
return 3;
}
else if("#".equals(op)) {
return 0;
}
return Integer.MAX_VALUE;
}
public String[] getItems(String str) {
ArrayList<String> list = new ArrayList<String>();
// Remove all blank spaces.
str = str.replaceAll("\\s", "");
int i = 0;
StringBuilder sBuilder = new StringBuilder();
while(i < str.length()) {
if(i == str.length() - 1) {
sBuilder.append(
Character.toString(str.charAt(i)));
list.add(sBuilder.toString());
}
if(!isOp(str.charAt(i))) {
sBuilder.append(
Character.toString(str.charAt(i)));
}
else {
if(sBuilder.length() > 0) {
list.add(sBuilder.toString());
sBuilder.delete(0, sBuilder.length());
}
list.add(Character.toString(str.charAt(i)));
}
++i;
}
list.add("#");
String[] result = new String[list.size()];
return list.toArray(result);
}
public ArrayList<String> change2PostfixExp(String normalExp) {
ArrayList<String> expList = new ArrayList<String>();
String[] items = getItems(normalExp);
opStack.clear();
expStack.clear();
opStack.push("#");
int i = 0;
while(i < items.length) {
//System.out.println(i + ":" + items[i]);
if(!isOp(items[i])) {
expList.add(items[i]);
}
else {
if(items[i].equals(")")){
while(!opStack.isEmpty() && !opStack.peek().equals("(")) {
expList.add(opStack.pop());
}
if(!opStack.isEmpty() && opStack.peek().equals("(")) {
opStack.pop();
}
++i;
continue;
}
if(items[i].equals("#")) {
while(!opStack.isEmpty() && !opStack.peek().equals("#")) {
expList.add(opStack.pop());
}
break;
}
if(!opStack.isEmpty()) {
while(!opStack.isEmpty()
&& (getOpPriority(opStack.peek()) >= getOpPriority(items[i])
&& !opStack.peek().equals("("))
) {
expList.add(opStack.pop());
}
opStack.push(items[i]);
}
}
++i;
}
return expList;
}
public double calculate(ArrayList<String> postfixExp) {
Stack<Double> calcStack = new Stack<Double>();
int i = 0;
String ite = null;
double result = Double.MAX_VALUE;
while(i < postfixExp.size()) {
ite = postfixExp.get(i);
if(!isOp(postfixExp.get(i))) {
calcStack.push(new Double(
Double.parseDouble(
postfixExp.get(i))
));
}
else {
double num2 = calcStack.peek();
calcStack.pop();
if(!calcStack.isEmpty()) {
double num1 = calcStack.peek();
calcStack.pop();
if("*".equals(ite)) {
result = num1 * num2;
}
else if("+".equals(ite)) {
result = num1 + num2;
}
else if("-".equals(ite)) {
result = num1 - num2;
}
else if("/".equals(ite)) {
result = num1 / num2;
}
System.out.println(num1 + "\t" + ite + "\t" + num2 + " = " + result);
calcStack.push(result);
}
}
++i;
}
return result;
}
}
分享到：
相关推荐
使用后缀表达式来实现表达式的计算。使用堆栈，把中缀表达式转换为后缀，支持运算符优先级。
在易语言中，脚本计算表达式是编程过程中的一个重要环节，它涉及到变量、运算符、函数和控制结构等多个方面。 易语言脚本计算表达式源码是指使用易语言编写的，能够解析并执行计算表达式的代码。这种源码通常包含...
中缀表达式转化为后缀表达式算法及后缀表达式算法的实现 中缀表达式转化为后缀表达式算法是计算机科学中的一种常见算法，用于将中缀表达式转化为后缀表达式。该算法广泛应用于编译器、解释器、计算器等领域。 中缀...
二叉树计算表达式 行之有效的代码，完全可以上交老师那种！
本主题主要关注如何使用C++实现一个计算表达式的算法。C++是一种强大且广泛应用的面向对象的编程语言，它提供了丰富的工具来处理这种问题。 首先，计算表达式通常涉及到解析、求值两个主要步骤。解析是将输入的字符...
逻辑表达式算法编译原理,是否汉字,读字符,是否运算符,是否逻辑运算符,指针回溯,跳过空格,跳过注释,外部接口_表达式计算,表达式计算,逻辑判断,函数调用,函数_位或,函数_测试,计算表达式数组,单个计算,输出状态
中缀表达式转化为后缀表达式算法及后缀表达式计算算法.doc.doc
中缀表达式转换为后缀表达式算法 该算法的核心思想是将中缀表达式转换为后缀表达式，然后通过后缀表达式计算出算术表达式的结果。该算法的步骤如下： 1. 定义一个 Node 结构体，结构体内部包含四个属性：操作符的...
总之，逆波兰表达式算法提供了一种简洁、高效的方式来计算数学表达式，其核心在于使用栈数据结构和运算符优先级规则。在`ExpressionParserUtil.java`文件中，我们可以找到具体的实现细节，这为我们理解和扩展该算法...
在易语言中，计算表达式是程序逻辑的重要组成部分，用于执行各种数学和逻辑运算。本文将深入探讨易语言中的计算表达式，以及其在不同场景下的速度对比。 首先，我们要理解计算表达式的概念。在易语言中，计算表达式...
树结构在计算表达式时具有显著优势，因为它们直观地反映了运算符的优先级和嵌套关系，使得计算过程更为简洁和高效。 首先，让我们深入理解什么是树结构。树是一种非线性的数据结构，由顶点（也称为节点）和连接这些...
本实验主题“数据结构计算表达式的值”着重于使用堆栈这一特殊的数据结构来解析和计算数学表达式。堆栈是一种后进先出（LIFO）的数据结构，非常适合解决逆波兰表示法（RPN，Reverse Polish Notation）或后缀表达式的...
在本项目中，我们主要探讨的是一个基于C++编程语言实现的算术逻辑表达式计算算法。这个工程是在Visual Studio 2010环境下构建的，因此，它充分考虑了与该IDE的兼容性，使得开发者能够直接在VS2010中打开、编译并运行...
在编程实现中，我们可以使用递归下降解析（Recursive Descent Parsing）或基于栈的算法（如Shunting-yard算法）将中缀表达式转换为后缀表达式，然后用栈来计算结果。Shunting-yard算法由Dijkstra提出，它首先将输入...
在这个堆栈实现后缀表达式算法的项目中，我们将在WinForm平台上构建一个能够处理这种表达式的计算器。 在后缀表达式中，运算符位于其操作数之后。例如，常规的乘法表达式 "2 * 3" 在后缀表达式中会写成 "2 3 *"。...
数据结构实验报告：中缀表达式转化为后缀表达式算法 中缀表达式转化为后缀表达式算法是数据结构实验报告的重要组成部分，该算法的实现是通过使用栈来实现的。栈是一种重要的数据结构，在程序设计中有着广泛的应用。...
1. 避免重复计算：对于相同的正则表达式，我们可以通过预编译构造出NFA，避免重复解析。 2. 避免回溯：利用NFA的特性，避免在处理量词时回溯。 3. 使用KMP或Boyer-Moore等高级字符串搜索算法，提高字符串匹配的效率...
计算表达式值是一个涉及到字符串处理、语法分析和算法设计的复杂问题。在实际编程中，我们需要考虑各种情况，例如错误处理（如非法字符、缺少括号等）、数值溢出以及用户界面设计等。后缀表达式的方法虽然更高效，但...
二叉树应用——计算表达式计算 二叉树是一种常用的数据结构，它可以用于表示复杂的计算表达式。二叉树的结构由节点组成，每个节点都可以有左右两个子节点。这种数据结构可以用于计算复杂的表达式，因为它可以将...
多字符串匹配算法（MultiStringRE）需要计算所有长度为l_min的前缀集合Pref(RE)。该算法类似于Commentz-Walter算法，只需要从Pref(RE)在文本中的初始位置开始验证RE是否匹配成功即可。 ##### Gnu的基于必要因子的...