====== 表达式求值 ======
表达式求值基本有两种算法,算法优先和语法分析
通常我们写的2+3×4叫中缀表达式,算法优先算法很依赖于和中缀表达式等价的后缀表达式,而借助二叉树求值本质也是一样的。
中缀转后缀的基本步骤
有个操作符栈opStack,保留暂时的优先级比较低的操作符,比如3+2*4,当碰到3时就要先入栈
碰到左括号(就一定进opStack,等再碰到左括号)时,将栈中直到左括号为止的所有操作符出栈使用,(使用指的是参与计算或拼二叉树,或拼后缀表达式)
碰到操作符,将栈顶开始往下的所有优先级大于等于本操作符的操作符出栈使用,本操作符入栈。
碰到操作数,直接使用。
贴一下代码先
package expression;
import java.util.Stack;
public class OperatorPrecedence
{
/**
* 暂不支持负号,但可以考虑,字符串开头的或操作符后紧挨的或括号后的减号必须算做负号
* @param infixStr
* @return
*/
public String infix2sufix(String infixStr){
StringBuilder rst = new StringBuilder();
Stack<Operator> opStack = new Stack<Operator>();
int len = infixStr.length();
for(int i=0;i<len;i++)
{
char c = infixStr.charAt(i);
//空格过滤掉
if(c == ' ')
{
rst.append(" ");
}
else if(Character.isDigit(c) || c=='.')
{
rst.append(c);
}
else if(c == '(')
{
opStack.push(new Operator('('));
}
else if(c == ')')
{
while(opStack.size()>0 && !(opStack.peek().equals(new Operator('('))))
{
rst.append(" "+opStack.pop().getSymbol());
}
//将左括号去除
assert opStack.peek().equals(new Operator('('));
opStack.pop();
}
else if(Operator.operators.contains(String.valueOf(c)))
{
Operator current = new Operator(c);
//栈空或当前优先级比栈顶的大才入栈,否则,栈内优先级小的挨次出栈拼结果
//pop out all the greater percedence operator
while(opStack.size()>0 && current.compareTo(opStack.peek())<=0)
{
rst.append(" "+opStack.pop().getSymbol());
}
//本操作符入栈
opStack.push(current);
rst.append(" ");
}
}
while(opStack.size()>0)
{
rst.append(" "+opStack.pop().getSymbol());
}
return rst.toString();
}
/**
* @param args
*/
public static void main(String[] args)
{
OperatorPrecedence o = new OperatorPrecedence();
System.out.println(o.infix2sufix("4-(4-3*5+(2*4)+100)/10"));
}
}
package expression;
import java.util.HashMap;
import java.util.LinkedList;
public class Operator implements Comparable
{
private static HashMap<Operator,Integer> ops = new HashMap<Operator,Integer>();
public static LinkedList<String> operators = new LinkedList<String>();
static{
ops.put(new Operator("("),0);
ops.put(new Operator("+"),1);
ops.put(new Operator("-"),1);
ops.put(new Operator("*"),100);
ops.put(new Operator("/"),100);
for(Operator o : ops.keySet())
{
operators.add(o.s);
}
}
private String s;
public String getSymbol()
{
return s;
}
@Override
public boolean equals(Object obj)
{
if(!(obj instanceof Operator))
{
return false;
}
return this.s.equals(((Operator)obj).s);
}
@Override
public int hashCode()
{
return this.s.hashCode();
}
public Operator(String s)
{
this.s = s;
}
public Operator(char c)
{
this.s = String.valueOf(c);
}
public int compareTo(Object o)
{
return ops.get(this) - ops.get(o);
}
/**
* @param args
*/
public static void main(String[] args)
{
System.out.println(ops.get(new Operator("@")));
}
}
1.
优化:
为避免特殊处理左括号,右括号,以及最后特殊处理操作符栈中的最后剩余操作符。也将他们定义了特定的优先级。
并在栈低放了个优先级很低的特殊的操作符#,初始化一个二维表来存储优先级关系,设定只有栈中(碰到),栈中#碰到#时,优先级为相等,
这时脱去括号。
这样写出的代码更简练一些。
见严蔚敏c语言版《数据结构》,这是偶的大学教程。
2.
其中描述的允许可以拼后缀表达式,
也可以另加一个栈存放操作数,当使用操作数时入栈,当使用操作符时,靠顶两个操作数出栈运算后结果再入栈。这样就直接得到表达式的结果。
如果把其中的运算换成“构建二叉树节点”,这里可以构建出一个表达式的二叉树来(中序遍历就是中缀表达式,后序遍历就是后缀)。
这样可以构建二叉树递归计算二叉树取结果或者直接取表达式的结果
3.
表达式求值的另一种方法,也是最灵活易懂的方式利用编译原理的语法分析。
可以收工根据语法分析来,也可以使用ANTLR这个工具
手工语法分析是要有些编译原理的知识,待续。。
如果用三方工具就简单得多,见另一篇
http://appofis.iteye.com/admin/blogs/743714
分享到:
相关推荐
通过基于真实网络流量的评测,比较了几种经典匹配算法在不同规则集上的匹配速度、内存占用和预处理时间等性能指标,并给出了不同需求场景下高效正则表达式匹配算法的选择建议,归纳了高性能正则表达式匹配算法的下...
设计了两个数值实验,利用几种重排算法对单道地震信号进行了计算和分析比较。结果表明:重排算法不仅能有效抑制交叉项,同时也能提高时频聚集性,从而获得更理想的局部信号特征。其中以重排Spectrogram分布的时频聚集...
我们在几种现实的RE规则集上测试了算法。 实验结果表明,它在存储效率和高吞吐量方面均具有良好的性能。 在Bro和Snort规则集上,它的效率是原始DFA的1422倍,而在lter规则集上,它的效率是原始DFA的27倍。
1.5 数据结构的存储方式有哪几种? 2.3 设计一个算法,求顺序表中值为x的结点的个数。 2.4 设计一个算法,将一个顺序表倒置,即如果顺序表各个结点值存储在一维数组a中,倒置的结果是使得数组a中的a[0]等于原来的...
电子商务:通过收集用户消费习惯、季节和产品生命周期的数据,建立算法模型来确定下一个月、几个月甚至一年的消费者需求。这样可以提高订单转化率。在营销方面,可以给买家贴标签,建立人群画像,针对不同人群精准...
都大于等于1,另一类小于等于-1 点到面的距离依据图中的公式计算 所以得到 total margin 的表达式如下,目标是最大化这个 margin,就需要最小化分母,于是变成了一个优化问题 2022年人工智能的常用十种算法全文共6...
图论(图论模型的建立,平面图,欧拉公式与五色定理,求强连通分量,求割点和桥,欧拉回路,AOV问题,AOE问题,最小生成树的三种算法,最短路的三种算法,标号法,差分约束系统,验证二分图,Konig定理,匈牙利算法...
本期任务:介绍算法中关于回溯思想的几个经典问题 【算法】【回溯篇】第1节:八皇后问题 【算法】【回溯篇】第2节:解数独问题 【算法】【回溯篇】第3节:正则表达式问题 【算法】【回溯篇】第4节:全排列问题 ...
包括栈的几种基本应用,封装成一个程序,包括表达式求值、括号匹配、进制转换的系列经典算法。
涵盖所有程序员必须掌握的50种算法 内容简介 《算法(第4版)》全面讲述算法和数据结构的必备知识,具有以下几大特色。 1、 算法领域的经典参考书:Sedgewick畅销著作的*版,反映了经过几十年演化而成的算法...
几种整周模糊度搜索技术,包括基于观测域的整周模糊度搜索!基于坐标域 的整周模糊度搜索和基于模糊度域的整周模糊度搜索;并分别介绍了几种搜 索技术中的典型算法,如双频伪距载波相位组合法!模糊度函数法和 LAMBDA算法...
四元数矩阵右特征值的计算可转化为它的复表示矩阵的特征值的计算问题,本文利用复表示矩阵的特殊结构给出了一种减少计算其特征值计算量的方法。 四元数矩阵计算中有一些新的问题是复矩阵计算中没有的内容。例如...
5.7 小结:选择一种排序算法 5.8 资源和参考资料 第6章 树 6.1 二叉树 6.1.1 树查找 6.1.2 节点插入 6.1.3 节点删除 6.1.4 二叉查找树的性能 6.1.5 AVL树 6.2 红黑树 6.3 伸展树 ...
迭代法是求方程近似根的一个重要方法,也是计算方法中的一种基本方法,它的算法简单,是用于求方程或方程组近似根的一种常用的算法设计方法。 牛顿迭代法是求方程根的重要方法之一,其最大优点是在方程f(x) = 0的...
然后,我们将讨论该算法在与散射振幅计算相关的几种技术中的应用,例如四维和六维自旋螺旋度形式主义,树级递归关系以及通过广义单一性进行的多环被乘数归约。 该方法具有良好的效率,并且可以随变量数量和问题的...
56.7 几种循环的比较 79 6.8 break 和 continue语句 79 6.8.1 break 语句 79 6.8.2 continue 语句 80 6.9 程序举例 81 7 数组 7.1 一维数组的定义和引用 82 7.1.1 一维数组的定义方式 82 7.1.2 一维数组元素的引用 ...
针对缓冲区有限的流水车间调度问题,分析了目标函数的特征,及目标函数与工件空闲时间...仿真实验结果表明,算法在求解质量和计算时间方面明显优于其他几种排序规则,并体现了目标函数表达式结构的特性及对解的适应性。
几种简单排序之间的比较 小结 问题 实验 编程作业 第4章 栈和队列 不同的结构类型 栈 队列 优先级队列 解析算术表达式 小结 问题 实验 编程作业 第5章 链表 链结点(Link) LinkList专题Applet ...
几种简单排序之间的比较 小结 问题 实验 编程作业 第4章 栈和队列 不同的结构类型 栈 队列 优先级队列 解析算术表达式 小结 问题 实验 编程作业 第5章 链表 链结点(Link) LinkList专题Applet ...