中缀表达式求值算法值
点击联系发帖人
时间：2014-10-24 05:59
表达式求值，中缀后缀转换，表达式递归直接求值等相关算法的实现_百度知道
表达式求值，中缀后缀转换，表达式递归直接求值等相关算法的实现
我有更好的答案
思路的话其实很简单，就是构建一棵二叉树，根节点和中间节点为运算符，叶子结点为运算数字。如 a + b*c， 构建为二叉树的话，就如下图：
c对于该二叉树，使用不同的遍历方式就可以得到不同的表达式了。遍历的代码很简单就不多说了。因此，你的问题主要可以分解为3个小问题：1。将后缀表达式转换为二叉树
该方法是最简单的。如a + b*c 的后缀表达式为 bc*a+.处理步骤如下：
1。建立一个栈S
2。从左到右读后缀表达式，读到数字就创建叶子节点，节点值为数字值。将节点压入栈S中，读到运算符则创建中间节点，并从栈中依次弹出两个节点分别为Y和X，作为中间节点的左右子节点，然后以“X 运算符 Y”的形式计算机出中间节点的值，再将此中间节点压加栈S中
3。就重...
为您推荐：
递归的相关知识
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁C++应用前缀、中缀建二叉树实现表达式求值，以二叉树的先序和中序次序建立二叉树的接口函数，已知二叉树的先序遍历次序及中序遍历次序，建立二叉树T，用后序遍历的方式对表达式树求值：
// 应用前缀、中缀建二叉树实现表达式求值
// 作者：王立波
#include &iostream&
#include &BinaryExpTree.h&
int main()
BinaryExpT
cout && &作为应用的一个小例子，此程序仅支持个位数算术运算！& &&
pch[256],ich[256];
cout && &请按二叉表达式树的前缀表示输入字符串：&&&
cout && &请按二叉表达式树的中缀表示输入字符串：&&&
int i = 0;
while(pch[i])
bt.Create (pch,ich,i);
cout && &表达式按后缀求值的结果为：&&&bt.Evaluate () &&
system(&pause&);
包含文件头：BinaryExpTree.h 代码：
#ifndef H_BinaryExpTree_H
#define H_BinaryExpTree_H
struct BTnode
class BinaryExpTree
BinaryExpTree(): m_root(NULL){}
~BinaryExpTree ();
void Create(char ch1[],char ch2[],int ); // 以二叉树的先序和中序次序建立二叉树的接口函数
int Evaluate();
BTnode *m_
void _DestroyBT(BTnode* &);
int _Evaluate(BTnode* &);
int _Opreate(const int &,const char &,const int &);
void _Create(BTnode * &,char ch1[],char ch2[],int ,int ,int &);//已知二叉树的先序遍历次序及中序遍历次序，建立二叉树T
//析构函数， 释放二叉树
BinaryExpTree :: ~BinaryExpTree( )
_DestroyBT(m_root);
//以二叉树的先序和中序次序建立二叉树的接口函数
void BinaryExpTree ::Create(char ch1[],char ch2[],int n)
int i = 0;
_Create( m_root,ch1,ch2,0,n-1,i);
// 初始条件: 二叉树p存在。操作结果: 销毁二叉树p
void BinaryExpTree::_DestroyBT(BTnode* &p)
_DestroyBT(p-&Lchild);
_DestroyBT(p-&Rchild);
int BinaryExpTree::Evaluate()
return(_Evaluate(m_root));
//用后序遍历的方式对表达式树求值
int BinaryExpTree ::_Evaluate(BTnode* &T)
if(!T-&Lchild && !T-&Rchild )
return T-&data - 48;
return _Opreate(_Evaluate(T-&Lchild),T-&data,_Evaluate(T-&Rchild));
//字符theta决定a与b 执行何种运算
int BinaryExpTree::_Opreate(const int &a,const char &theta,const int &b)
switch(theta){
case'+' : c = a +
case'-' : c = a -
case'*' : c=
case'/' : c = a /
//已知二叉树的先序遍历次序及中序遍历次序，建立二叉树T
void BinaryExpTree :: _Create (BTnode* &T,char ch1[],char ch2[],int low,int high,int &k)
if(low & high)
T = new BT
T-&data = ch1[k];
for ( i =i &= high&&ch2[i] != ch1[k];i++);
if(ch2[i] == ch1[k]){
_Create (T-&Lchild,ch1,ch2,low,i-1,k);
_Create (T-&Rchild,ch1,ch2,i+1,high,k);
本类推荐文章
本类最新更新
最新源码下载表达式求值的递归算法
表达式求值的递归算法
表达式求值,一般采用逆波兰算法,即转化为后缀表达式再进行计算。这当然很好。可是这个算法逻辑上不那么直观，如果是笔试或机考的话，除非你最近恰好看过该算法，或者你就是研究这些算法的，一般估计很难在限定的时间内理清头绪并写出代码。
如果直接采用中缀表达式求值，就更复杂了。如果不是准备充分，相信很难在笔试/机考的情况下完成代码。本人早几天去笔试就碰到这个题目,两小时,机考.当时看到这个题目，想了一个小时，也没想起逆波兰算法。在学校学的东西基本都忘的差不多了。最后只好直接对中缀表达式求值。结果当然是没搞定。还好该职位并不是很有吸引力的，不然就亏大了。
&事后想想，这个问题应该用递归的方法解决。这才是逻辑简单的，适合应试的算法。不废话，先贴代码。
(下面的代码支持 加减乘除，乘方，括号。没有进行错误检查。)&
#include "stdafx.h"
#include &stdlib.h&
#include &string.h&
#include &assert.h&
#include &math.h&
//去括号,当整个表达式被一个括号包围时,可直接去掉.
void DelBracket(char *expre)// 比如: (3+4* (2-1)+5 )
& & & & if(expre[0]=='(')
& & & & & & & & int& level = 0;
& & & & & & & & char *
& & & & & & & & for(pos=*++pos)
& & & & & & & & {
& & & & & & & & & & & & if(*pos=='(')& & & ++
& & & & & & & & & & & & else if(*pos==')') --
& & & & & & & & & & & & if(level==0)//找到匹配的括号.
& & & & & & & & & & & & & & & & break;
& & & & & & & & }
& & & & & & & & if(*(pos+1)==0)//下一个字符是结尾
& & & & & & & & {
& & & & & & & & & & & & *pos = 0;
& & & & & & & & & & & & memmove(expre,expre+1,pos-expre);
& & & & & & & & }
bool IsNum(const char *str,double & v)
& & & & char *
& & & & double temp = strtod(str,&end);
& & & & if(end==str+strlen(str))
& & & & & & & & v =
& & & & & & & & return true;
& & & & return false;
int FindOp(const char *expre)//找出最后一个优先级最低的运算符.
& & & & const char *
& & & & int& level = 0;//当前位置的括号层数
& & & & int& pos1 = -1; //最后一个 + - 出现的位置.
& & & & int& pos2 = -1; //最后一个 * / 出现的位置.
& & & & int& pos3 = -1; //最后一个 ^& &出现的位置.
& & & & for(pos= * ++pos)
& & & & & & & & if(*pos=='(')& & & ++
& & & & & & & & else if(*pos==')') --
& & & & & & & &
& & & & & & & & if(level==0)//不在括号中.
& & & & & & & & {
& & & & & & & & & & & & if(*pos=='+'||*pos=='-')
& & & & & & & & & & & & {
& & & & & & & & & & & & & & & & pos1 = pos -
& & & & & & & & & & & & }
& & & & & & & & & & & & else if(*pos=='*'||*pos=='/')
& & & & & & & & & & & & {
& & & & & & & & & & & & & & & & pos2 = pos -
& & & & & & & & & & & & }
& & & & & & & & & & & & else if(*pos=='^')
& & & & & & & & & & & & {
& & & & & & & & & & & & & & & & pos3 = pos -
& & & & & & & & & & & & }
& & & & & & & & }
& & & & int op_pos = -1;
& & & & if(pos1!=-1)& & & op_pos = pos1;
& & & & else if(pos2!=-1) op_pos = pos2;
& & & & else if(pos3!=-1) op_pos = pos3;
& & & & else {} //找不到运算符.
& & & & return op_
//把表达式拆成 a op b 的形式,并计算其值.
double DivExpression(const char *expre)
& & & & double result = ;
& & & & char buf[300];
& & & & strcpy(buf,expre);
& & & & DelBracket(buf);//去括号,当整个表达式被一个括号包围时,可直接去掉.
& & & & int pos = FindOp(buf);//找到最右边的最低优先级的运算符.
& & & & if(pos!=-1)//能拆成 a op b 的形式
& & & & & & & & char a[300];
& & & & & & & & char b[300];
& & & & & & & & strncpy(a,buf,pos);
& & & & & & & & a[pos] = 0;
& & & & & & & & char op = buf[pos];
& & & & & & & & ++
& & & & & & & & strcpy(b,buf+pos);
& & & & & & & & double a_v,b_v;
& & & & & & & & if(strlen(a)==0) a_v = 0.0; //a是空字符串.
& & & & & & & & else if(!IsNum(a,a_v))
& & & & & & & & & & & && a_v = DivExpression(a);
& & & & & & & & if(!IsNum(b,b_v))
& & & & & & & & & & & & b_v =DivExpression(b);&
& & & & & & & & switch(op)
& & & & & & & & {
& & & & & & & & case& '+':& result = a_v+b_v;& & & &break;
& & & & & & & & case& '-':& result = a_v-b_v;& & & &break;
& & & & & & & & case& '*':& result = a_v*b_v;& & & &break;
& & & & & & & & case& '/':& result = a_v/b_v;& & & &break;
& & & & & & & & case& '^':& result = pow(a_v,b_v);& break;
& & & & & & & & default:& & assert(0);& & & & & & & break;
& & & & & & & & }
& & else//找不到二元操作符.可能是一元/三元操作符表达式.
& & & & & & & & IsNum(buf,result);//这里只支持表达式就是一个数.
& & & & return
int main(int argc, char* argv[])
& & & & typedef struct
& & & & & & & & char *
& & & & & & & & double
& & & & }I
& & & & Item test[] = {
& & & & & & & & {"1",& & & &1},
& & & & & & & & {"1+2",& & &3},
& & & & & & & & {"1-2+4",& &3},
& & & & & & & & {"1+2-4",& -1},
& & & & & & & & {"1+2*4",& &9},
& & & & & & & & {"1+4/2",& &3},
& & & & & & & & {"3*2-4/1", 2},
& & & & & & & & {"3^2-4*2", 1},
& & & & & & & & {"5-(3+1)", 1},
& & & & & & & & {"5-(3+1)/2", 3},
& & & & & & & & {"5^2*3-(4+12/(3-1))/2", 70},
& & & & & & & & {"3^3*((6+3)-5)",108},
& & & & & & & & {"-(3+8)", -11},
& & & & & & & & {"-11+(-3)",-14},
& & & & & & & & {"-(-5)*3",15},
& & & & & & & & {"(-5)^2",25},
& & & & & & & & {"-5^2",-25},
& & & & & & & & {"-5^(-2)",-0.04},
& & & & & & & & {"5*(3+1)/2^2", 5},
& & & & };
& & & & for(int i=0;i&sizeof(test)/sizeof(Item);++i)
& & & & & & & & double re = DivExpression(test[i].expre);
& & & & & & & & double diff = re-test[i].result;
& & & & & & & & printf("%s = %.2f \t\t\t\t\t",test[i].expre,test[i].result);
& & & & & & & & if(diff&0.0001 && diff&-0.0001)
& & & & & & & & {
& & & & & & & & & & & & printf("ok\n");
& & & & & & & & }
& & & & & & & & else
& & & & & & & & {
& & & & & & & & & & & & printf("error: %.2f\n",re);
& & & & & & & & }
& & & & return 0;
&基本思路是这样的：一个表达式，可视为 a op b的形式，其中op是运算符。如果a，b都是操作数，就可以直接求值了。如果a，b是表达式，则还需再分解为 a op b 的形式，直到分解为全部是数为止。
&这其中有几点要注意的：
1、分解的时候，不能拆括号。即不能把一个括号的内容分解到运算符的两边。
2、只能先从低优先级运算符开始。比如：2*3+4/5，只能从+号开始分解。
3、同一运算符，从最右边的开始分解。比如：2-3+4，只能从 + 号开始分解。
4、如果一个表达式整个被括号包围，该括号可去掉。
5、对于(-5)这样的表达式，有一个小技巧，看成是 (0-5)，即如果 a为空的话，则对于的值视为0。这就避免了还要考虑一元运算符。
上面的原则，1,2,3都好理解，都对应到运算规则：a，先算括号内的。 b，先乘方，再乘除，最后加减。c，同优先级，从左到右。
这3条规则保证拆分后的运算顺序和原来的是一样的。
第4条规则，是程序上的需要。因为不能拆开括号，如果一个表达式整个是一个括号，就没办法往下拆分了。所以必须去括号。
规则5是为了统一为二元运算符，这样实现起来简单。
上面的代码没有考虑非法的表达式。如果要考虑，就复杂了。包括括号不匹配，非法字符，多个运算符串联，除0错误等等。
发表评论：
TA的最新馆藏[转]&[转]&[转]&[转]& 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
正在努力加载中...
设计并实现将一个中缀表达式转换成逆波兰式,然后对此逆波兰表达式求值的算法。
下载积分：870
内容提示：设计并实现将一个中缀表达式转换成逆波兰式,然后对此逆波兰表达式求值的算法。
文档格式：DOC|
浏览次数：83|
上传日期： 09:25:43|
文档星级：
该用户还上传了这些文档
设计并实现将一个中缀表达式转换成逆波兰式,然后对此
官方公共微信数据结构学习（C++）――栈应用（表达式求值）数据结构学习（C++）――栈应用（表达式求值）
BASICtype#ifndef Expression_H#define Expression_H&#include "List.h"#include "Stack.h"&#define INFIX 0#define POSTFIX 1#define OPND 4#define OPTR 8&template &class Type& class ExpNode{public:&&&&&& &&&&&& union {T};&&&&&& ExpNode() : type(INFIX), optr('=') {}&&&&&& ExpNode(Type opnd) : type(OPND), opnd(opnd) {}&&&&&& ExpNode(char optr) : type(OPTR), optr(optr) {}};&template &class Type& class Expression : List&ExpNode&Type& &{public:&&&&&& void Input()&&&&&& {&&&&&& &&&&&& MakeEmpty(); Get()-&type =INFIX;&&&&&&&&&&&&& cout && endl && "输入表达式，以＝结束输入" &&&&&&&&&&&&&&& T char optr = ' ';&&&&&&&&&&&&& while (optr != '=')&&&&&&&&&&&&& {&&&&&&&&&&&&& &&&&&& cin && &&&&&&&&&&&&&&&&&&&& if (opnd != 0)&&&&&&&&&&&&&&&&&&&& {&&&&&&&&&&&&&&&&&&&& &&&&&& ExpNode&Type& newopnd(opnd);&&&&&&&&&&&&&&&&&&&& &&&&&& LastInsert(newopnd);&&&&&&&&&&&&&&&&&&&& }&&&&&&&&&&&&& &&&&&& cin &&&&&&&&&&&&&&& &&&&&& ExpNode&Type& newoptr(optr);&&&&&&&&&&&&& &&&&&& LastInsert(newoptr);&&&&&&&&&&&&&&&&&&&& &&&&&&&&&&&&& }&&&&&& }&&&&&&& void Print()&&&&&& {&&&&&& &&&&&& First();&&&&&&&&&&&&& cout &&&&&&&&&&&&&&& for (ExpNode&Type& *p = Next(); p != NULL; p = Next() )&&&&&&&&&&&&& {&&&&&&&&&&&&& &&&&&& switch (p-&type)&&&&&&&&&&&&&&&&&&&& {&&&&&&&&&&&&& &&&&&& case OPND:&&&&&&&&&&&&&&&&&&&& &&&&&& cout && p-&&&&&&&&&&&&&& &&&&&& case OPTR:&&&&&&&&&&&&&&&&&&&& &&&&&& cout && p-&&&&&&&&&&&&&& &&&&&& default:&&&&&&&&&&&&&&&&&&&& }&&&&&&&&&&&&& &&&&&& cout && ' ';&&&&&&&&&&&&& }&&&&&&&&&&&&& cout &&&&&&&& }&&&&&&& Expression & Postfix() //将中缀表达式转变为后缀表达式&&&&&& {&&&&&& &&&&&& First();&&&&&&&&&&&&& if (Get()-&type == POSTFIX) return *&&&&&& &&&&&& Stack&char& s.Push('=');&&&&&& &&&&&& E&&&&&& &&&&&& ExpNode&Type& *p = Next();&&&&&&&&&&&&& while (p != NULL)&&&&&&&&&&&&& {&&&&&&&&&&&&& &&&&&& switch (p-&type)&&&&&&&&&&&&&&&&&&&& {&&&&&&&&&&&&& &&&&&& case OPND:&&&&&&&&&&&&&&&&&&&& &&&&&& temp.LastInsert(*p); p = Next();&&&&&&&&&&&&& &&&&&& case OPTR:&&&&&&&&&&&&&&&&&&&& &&&&&& while (isp(s.GetTop()) & icp(p-&optr) )&&&&&&&&&&&&&&&&&&&& &&&&&& {&&&&&&&&&&&&&&&&&&&& &&&&&& &&&&&& ExpNode&Type& newoptr(s.Pop());&&&&&&&&&&&&&&&&&&&& &&&&&& &&&&&& temp.LastInsert(newoptr);&&&&&&&&&&&&&&&&&&&& &&&&&& }&&&&&&&&&&&&&&&&&&&& &&&&&& if (isp(s.GetTop()) == icp(p-&optr) )&&&&&&&&&&&&&&&&&&&& &&&&&& {&&&&&&&&&&&&&&&&&&&& &&&&&& &&&&&& s.Pop(); p =Next();&&&&&&&&&&&&&&&&&&&& &&&&&& }&&&&&&&&&&&&&&&&&&&& &&&&&& s.Push(p-&optr); p = Next();&&&&&&&&&&&&& &&&&&& default:&&&&&&&&&&&&&&&&&&&& }&&&&&&&&&&&&& }&&&&&&&&&&&&& *this =&&&&&& &&&&&& pGetFirst()-&data.type = POSTFIX;&&&&&&&&&&&&& return *&&&&&& }&&&&&&& Type Calculate()&&&&&& {&&&&&& &&&&&& Expression temp = *&&&&&&&&&&&&& if (pGetFirst()-&data.type != POSTFIX) temp.Postfix();&&&&&& &&&&&& Stack&Type& Type left,&&&&&&&&&&&&& for (ExpNode&Type& *p = temp.Next(); p != NULL; p = temp.Next())&&&&&&&&&&&&& {&&&&&&&&&&&&& &&&&&& switch (p-&type)&&&&&&&&&&&&&&&&&&&& {&&&&&&&&&&&&& &&&&&& case OPND:&&&&&&&&&&&&&&&&&&&& &&&&&& s.Push(p-&opnd);&&&&&&&&&&&&& &&&&&& case OPTR:&&&&&&&&&&&&&&&&&&&& &&&&&& right = s.Pop(); left = s.Pop();&&&&&&&&&&&&&&&&&&&& &&&&&& switch (p-&optr)&&&&&&&&&&&&&&&&&&&& &&&&&& {&&&&&&&&&&&&&&&&&&&& &&&&&& case '+': s.Push(left + right);&&&&&&&&&&&&&&&&&&&& &&&&&& case '-': s.Push(left - right);&&&&&&&&&&&&&&&&&&&& &&&&&& case '*': s.Push(left * right);&&&&&&&&&&&&&&&&&&&& &&&&&& case '/': if (right != 0) s.Push(left/right); else return 0;//&&&&&&&&&&&&&&&&&& &&&&&& case '%': if (right != 0) s.Push(left%right); else return 0;//&&&&&&&&&&&&&&&&&& &&&&&& case '^': s.Push(Power(left, right));&&&&&&&&&&&&&&&&&&&& &&&&&& default:&&&&&&&&&&&&&&&&&&&& &&&&&& }&&&&&&&&&&&&& &&&&&& default:&&&&&&&&&&&&&&&&&&&& }&&&&&&&&&&&&& }&&&&&&&&&&&&& return s.Pop();&&&&&& }&private:&&&&&& int isp(char optr)&&&&&& {&&&&&&&&&&&&& switch (optr)&&&&&&&&&&&&& {&&&&&&&&&&&&& case '=': return 0;&&&&&&&&&&&&& case '(': return 1;&&&&&&&&&&&&& case '^': return 7;&&&&&&&&&&&&& case '*': return 5;&&&&&&&&&&&&& case '/': return 5;&&&&&&&&&&&&& case '%': return 5;&&&&&&&&&&&&& case '+': return 3;&&&&&&&&&&&&& case '-': return 3;&&&&&&&&&&&&& case ')': return 8;&&&&&& &&&&&& default: return 0;&&&&&&&&&&&&& }&&&&&& }&&&&&&& int icp(char optr)&&&&&& {&&&&&&&&&&&&& switch (optr)&&&&&&&&&&&&& {&&&&&&&&&&&&& case '=': return 0;&&&&&&&&&&&&& case '(': return 8;&&&&&&&&&&&&& case '^': return 6;&&&&&&&&&&&&& case '*': return 4;&&&&&&&&&&&&& case '/': return 4;&&&&&&&&&&&&& case '%': return 4;&&&&&&&&&&&&& case '+': return 2;&&&&&&&&&&&&& case '-': return 2;&&&&&&&&&&&&& case ')': return 1;&&&&&& &&&&&& default: return 0;&&&&&&&&&&&&& }&&&&&& }&};&#endifll000llCalculate()^Power()lisp()icp()^^9 &}
表达式求值，中缀后缀转换，表达式递归直接求值等相关算法的实现
我有更好的答案
思路的话其实很简单，就是构建一棵二叉树，根节点和中间节点为运算符，叶子结点为运算数字。如 a + b*c， 构建为二叉树的话，就如下图：
c对于该二叉树，使用不同的遍历方式就可以得到不同的表达式了。遍历的代码很简单就不多说了。因此，你的问题主要可以分解为3个小问题：1。将后缀表达式转换为二叉树
该方法是最简单的。如a + b*c 的后缀表达式为 bc*a+.处理步骤如下：
1。建立一个栈S
2。从左到右读后缀表达式，读到数字就创建叶子节点，节点值为数字值。将节点压入栈S中，读到运算符则创建中间节点，并从栈中依次弹出两个节点分别为Y和X，作为中间节点的左右子节点，然后以“X 运算符 Y”的形式计算机出中间节点的值，再将此中间节点压加栈S中
3。就重...
为您推荐：
递归的相关知识
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁C++应用前缀、中缀建二叉树实现表达式求值，以二叉树的先序和中序次序建立二叉树的接口函数，已知二叉树的先序遍历次序及中序遍历次序，建立二叉树T，用后序遍历的方式对表达式树求值：
// 应用前缀、中缀建二叉树实现表达式求值
// 作者：王立波
#include &iostream&
#include &BinaryExpTree.h&
int main()
BinaryExpT
cout && &作为应用的一个小例子，此程序仅支持个位数算术运算！& &&
pch[256],ich[256];
cout && &请按二叉表达式树的前缀表示输入字符串：&&&
cout && &请按二叉表达式树的中缀表示输入字符串：&&&
int i = 0;
while(pch[i])
bt.Create (pch,ich,i);
cout && &表达式按后缀求值的结果为：&&&bt.Evaluate () &&
system(&pause&);
包含文件头：BinaryExpTree.h 代码：
#ifndef H_BinaryExpTree_H
#define H_BinaryExpTree_H
struct BTnode
class BinaryExpTree
BinaryExpTree(): m_root(NULL){}
~BinaryExpTree ();
void Create(char ch1[],char ch2[],int ); // 以二叉树的先序和中序次序建立二叉树的接口函数
int Evaluate();
BTnode *m_
void _DestroyBT(BTnode* &);
int _Evaluate(BTnode* &);
int _Opreate(const int &,const char &,const int &);
void _Create(BTnode * &,char ch1[],char ch2[],int ,int ,int &);//已知二叉树的先序遍历次序及中序遍历次序，建立二叉树T
//析构函数， 释放二叉树
BinaryExpTree :: ~BinaryExpTree( )
_DestroyBT(m_root);
//以二叉树的先序和中序次序建立二叉树的接口函数
void BinaryExpTree ::Create(char ch1[],char ch2[],int n)
int i = 0;
_Create( m_root,ch1,ch2,0,n-1,i);
// 初始条件: 二叉树p存在。操作结果: 销毁二叉树p
void BinaryExpTree::_DestroyBT(BTnode* &p)
_DestroyBT(p-&Lchild);
_DestroyBT(p-&Rchild);
int BinaryExpTree::Evaluate()
return(_Evaluate(m_root));
//用后序遍历的方式对表达式树求值
int BinaryExpTree ::_Evaluate(BTnode* &T)
if(!T-&Lchild && !T-&Rchild )
return T-&data - 48;
return _Opreate(_Evaluate(T-&Lchild),T-&data,_Evaluate(T-&Rchild));
//字符theta决定a与b 执行何种运算
int BinaryExpTree::_Opreate(const int &a,const char &theta,const int &b)
switch(theta){
case'+' : c = a +
case'-' : c = a -
case'*' : c=
case'/' : c = a /
//已知二叉树的先序遍历次序及中序遍历次序，建立二叉树T
void BinaryExpTree :: _Create (BTnode* &T,char ch1[],char ch2[],int low,int high,int &k)
if(low & high)
T = new BT
T-&data = ch1[k];
for ( i =i &= high&&ch2[i] != ch1[k];i++);
if(ch2[i] == ch1[k]){
_Create (T-&Lchild,ch1,ch2,low,i-1,k);
_Create (T-&Rchild,ch1,ch2,i+1,high,k);
本类推荐文章
本类最新更新
最新源码下载表达式求值的递归算法
表达式求值的递归算法
表达式求值,一般采用逆波兰算法,即转化为后缀表达式再进行计算。这当然很好。可是这个算法逻辑上不那么直观，如果是笔试或机考的话，除非你最近恰好看过该算法，或者你就是研究这些算法的，一般估计很难在限定的时间内理清头绪并写出代码。
如果直接采用中缀表达式求值，就更复杂了。如果不是准备充分，相信很难在笔试/机考的情况下完成代码。本人早几天去笔试就碰到这个题目,两小时,机考.当时看到这个题目，想了一个小时，也没想起逆波兰算法。在学校学的东西基本都忘的差不多了。最后只好直接对中缀表达式求值。结果当然是没搞定。还好该职位并不是很有吸引力的，不然就亏大了。
&事后想想，这个问题应该用递归的方法解决。这才是逻辑简单的，适合应试的算法。不废话，先贴代码。
(下面的代码支持 加减乘除，乘方，括号。没有进行错误检查。)&
#include "stdafx.h"
#include &stdlib.h&
#include &string.h&
#include &assert.h&
#include &math.h&
//去括号,当整个表达式被一个括号包围时,可直接去掉.
void DelBracket(char *expre)// 比如: (3+4* (2-1)+5 )
& & & & if(expre[0]=='(')
& & & & & & & & int& level = 0;
& & & & & & & & char *
& & & & & & & & for(pos=*++pos)
& & & & & & & & {
& & & & & & & & & & & & if(*pos=='(')& & & ++
& & & & & & & & & & & & else if(*pos==')') --
& & & & & & & & & & & & if(level==0)//找到匹配的括号.
& & & & & & & & & & & & & & & & break;
& & & & & & & & }
& & & & & & & & if(*(pos+1)==0)//下一个字符是结尾
& & & & & & & & {
& & & & & & & & & & & & *pos = 0;
& & & & & & & & & & & & memmove(expre,expre+1,pos-expre);
& & & & & & & & }
bool IsNum(const char *str,double & v)
& & & & char *
& & & & double temp = strtod(str,&end);
& & & & if(end==str+strlen(str))
& & & & & & & & v =
& & & & & & & & return true;
& & & & return false;
int FindOp(const char *expre)//找出最后一个优先级最低的运算符.
& & & & const char *
& & & & int& level = 0;//当前位置的括号层数
& & & & int& pos1 = -1; //最后一个 + - 出现的位置.
& & & & int& pos2 = -1; //最后一个 * / 出现的位置.
& & & & int& pos3 = -1; //最后一个 ^& &出现的位置.
& & & & for(pos= * ++pos)
& & & & & & & & if(*pos=='(')& & & ++
& & & & & & & & else if(*pos==')') --
& & & & & & & &
& & & & & & & & if(level==0)//不在括号中.
& & & & & & & & {
& & & & & & & & & & & & if(*pos=='+'||*pos=='-')
& & & & & & & & & & & & {
& & & & & & & & & & & & & & & & pos1 = pos -
& & & & & & & & & & & & }
& & & & & & & & & & & & else if(*pos=='*'||*pos=='/')
& & & & & & & & & & & & {
& & & & & & & & & & & & & & & & pos2 = pos -
& & & & & & & & & & & & }
& & & & & & & & & & & & else if(*pos=='^')
& & & & & & & & & & & & {
& & & & & & & & & & & & & & & & pos3 = pos -
& & & & & & & & & & & & }
& & & & & & & & }
& & & & int op_pos = -1;
& & & & if(pos1!=-1)& & & op_pos = pos1;
& & & & else if(pos2!=-1) op_pos = pos2;
& & & & else if(pos3!=-1) op_pos = pos3;
& & & & else {} //找不到运算符.
& & & & return op_
//把表达式拆成 a op b 的形式,并计算其值.
double DivExpression(const char *expre)
& & & & double result = ;
& & & & char buf[300];
& & & & strcpy(buf,expre);
& & & & DelBracket(buf);//去括号,当整个表达式被一个括号包围时,可直接去掉.
& & & & int pos = FindOp(buf);//找到最右边的最低优先级的运算符.
& & & & if(pos!=-1)//能拆成 a op b 的形式
& & & & & & & & char a[300];
& & & & & & & & char b[300];
& & & & & & & & strncpy(a,buf,pos);
& & & & & & & & a[pos] = 0;
& & & & & & & & char op = buf[pos];
& & & & & & & & ++
& & & & & & & & strcpy(b,buf+pos);
& & & & & & & & double a_v,b_v;
& & & & & & & & if(strlen(a)==0) a_v = 0.0; //a是空字符串.
& & & & & & & & else if(!IsNum(a,a_v))
& & & & & & & & & & & && a_v = DivExpression(a);
& & & & & & & & if(!IsNum(b,b_v))
& & & & & & & & & & & & b_v =DivExpression(b);&
& & & & & & & & switch(op)
& & & & & & & & {
& & & & & & & & case& '+':& result = a_v+b_v;& & & &break;
& & & & & & & & case& '-':& result = a_v-b_v;& & & &break;
& & & & & & & & case& '*':& result = a_v*b_v;& & & &break;
& & & & & & & & case& '/':& result = a_v/b_v;& & & &break;
& & & & & & & & case& '^':& result = pow(a_v,b_v);& break;
& & & & & & & & default:& & assert(0);& & & & & & & break;
& & & & & & & & }
& & else//找不到二元操作符.可能是一元/三元操作符表达式.
& & & & & & & & IsNum(buf,result);//这里只支持表达式就是一个数.
& & & & return
int main(int argc, char* argv[])
& & & & typedef struct
& & & & & & & & char *
& & & & & & & & double
& & & & }I
& & & & Item test[] = {
& & & & & & & & {"1",& & & &1},
& & & & & & & & {"1+2",& & &3},
& & & & & & & & {"1-2+4",& &3},
& & & & & & & & {"1+2-4",& -1},
& & & & & & & & {"1+2*4",& &9},
& & & & & & & & {"1+4/2",& &3},
& & & & & & & & {"3*2-4/1", 2},
& & & & & & & & {"3^2-4*2", 1},
& & & & & & & & {"5-(3+1)", 1},
& & & & & & & & {"5-(3+1)/2", 3},
& & & & & & & & {"5^2*3-(4+12/(3-1))/2", 70},
& & & & & & & & {"3^3*((6+3)-5)",108},
& & & & & & & & {"-(3+8)", -11},
& & & & & & & & {"-11+(-3)",-14},
& & & & & & & & {"-(-5)*3",15},
& & & & & & & & {"(-5)^2",25},
& & & & & & & & {"-5^2",-25},
& & & & & & & & {"-5^(-2)",-0.04},
& & & & & & & & {"5*(3+1)/2^2", 5},
& & & & };
& & & & for(int i=0;i&sizeof(test)/sizeof(Item);++i)
& & & & & & & & double re = DivExpression(test[i].expre);
& & & & & & & & double diff = re-test[i].result;
& & & & & & & & printf("%s = %.2f \t\t\t\t\t",test[i].expre,test[i].result);
& & & & & & & & if(diff&0.0001 && diff&-0.0001)
& & & & & & & & {
& & & & & & & & & & & & printf("ok\n");
& & & & & & & & }
& & & & & & & & else
& & & & & & & & {
& & & & & & & & & & & & printf("error: %.2f\n",re);
& & & & & & & & }
& & & & return 0;
&基本思路是这样的：一个表达式，可视为 a op b的形式，其中op是运算符。如果a，b都是操作数，就可以直接求值了。如果a，b是表达式，则还需再分解为 a op b 的形式，直到分解为全部是数为止。
&这其中有几点要注意的：
1、分解的时候，不能拆括号。即不能把一个括号的内容分解到运算符的两边。
2、只能先从低优先级运算符开始。比如：2*3+4/5，只能从+号开始分解。
3、同一运算符，从最右边的开始分解。比如：2-3+4，只能从 + 号开始分解。
4、如果一个表达式整个被括号包围，该括号可去掉。
5、对于(-5)这样的表达式，有一个小技巧，看成是 (0-5)，即如果 a为空的话，则对于的值视为0。这就避免了还要考虑一元运算符。
上面的原则，1,2,3都好理解，都对应到运算规则：a，先算括号内的。 b，先乘方，再乘除，最后加减。c，同优先级，从左到右。
这3条规则保证拆分后的运算顺序和原来的是一样的。
第4条规则，是程序上的需要。因为不能拆开括号，如果一个表达式整个是一个括号，就没办法往下拆分了。所以必须去括号。
规则5是为了统一为二元运算符，这样实现起来简单。
上面的代码没有考虑非法的表达式。如果要考虑，就复杂了。包括括号不匹配，非法字符，多个运算符串联，除0错误等等。
发表评论：
TA的最新馆藏[转]&[转]&[转]&[转]& 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
正在努力加载中...
设计并实现将一个中缀表达式转换成逆波兰式,然后对此逆波兰表达式求值的算法。
下载积分：870
内容提示：设计并实现将一个中缀表达式转换成逆波兰式,然后对此逆波兰表达式求值的算法。
文档格式：DOC|
浏览次数：83|
上传日期： 09:25:43|
文档星级：
该用户还上传了这些文档
设计并实现将一个中缀表达式转换成逆波兰式,然后对此
官方公共微信数据结构学习（C++）――栈应用（表达式求值）数据结构学习（C++）――栈应用（表达式求值）
BASICtype#ifndef Expression_H#define Expression_H&#include "List.h"#include "Stack.h"&#define INFIX 0#define POSTFIX 1#define OPND 4#define OPTR 8&template &class Type& class ExpNode{public:&&&&&& &&&&&& union {T};&&&&&& ExpNode() : type(INFIX), optr('=') {}&&&&&& ExpNode(Type opnd) : type(OPND), opnd(opnd) {}&&&&&& ExpNode(char optr) : type(OPTR), optr(optr) {}};&template &class Type& class Expression : List&ExpNode&Type& &{public:&&&&&& void Input()&&&&&& {&&&&&& &&&&&& MakeEmpty(); Get()-&type =INFIX;&&&&&&&&&&&&& cout && endl && "输入表达式，以＝结束输入" &&&&&&&&&&&&&&& T char optr = ' ';&&&&&&&&&&&&& while (optr != '=')&&&&&&&&&&&&& {&&&&&&&&&&&&& &&&&&& cin && &&&&&&&&&&&&&&&&&&&& if (opnd != 0)&&&&&&&&&&&&&&&&&&&& {&&&&&&&&&&&&&&&&&&&& &&&&&& ExpNode&Type& newopnd(opnd);&&&&&&&&&&&&&&&&&&&& &&&&&& LastInsert(newopnd);&&&&&&&&&&&&&&&&&&&& }&&&&&&&&&&&&& &&&&&& cin &&&&&&&&&&&&&&& &&&&&& ExpNode&Type& newoptr(optr);&&&&&&&&&&&&& &&&&&& LastInsert(newoptr);&&&&&&&&&&&&&&&&&&&& &&&&&&&&&&&&& }&&&&&& }&&&&&&& void Print()&&&&&& {&&&&&& &&&&&& First();&&&&&&&&&&&&& cout &&&&&&&&&&&&&&& for (ExpNode&Type& *p = Next(); p != NULL; p = Next() )&&&&&&&&&&&&& {&&&&&&&&&&&&& &&&&&& switch (p-&type)&&&&&&&&&&&&&&&&&&&& {&&&&&&&&&&&&& &&&&&& case OPND:&&&&&&&&&&&&&&&&&&&& &&&&&& cout && p-&&&&&&&&&&&&&& &&&&&& case OPTR:&&&&&&&&&&&&&&&&&&&& &&&&&& cout && p-&&&&&&&&&&&&&& &&&&&& default:&&&&&&&&&&&&&&&&&&&& }&&&&&&&&&&&&& &&&&&& cout && ' ';&&&&&&&&&&&&& }&&&&&&&&&&&&& cout &&&&&&&& }&&&&&&& Expression & Postfix() //将中缀表达式转变为后缀表达式&&&&&& {&&&&&& &&&&&& First();&&&&&&&&&&&&& if (Get()-&type == POSTFIX) return *&&&&&& &&&&&& Stack&char& s.Push('=');&&&&&& &&&&&& E&&&&&& &&&&&& ExpNode&Type& *p = Next();&&&&&&&&&&&&& while (p != NULL)&&&&&&&&&&&&& {&&&&&&&&&&&&& &&&&&& switch (p-&type)&&&&&&&&&&&&&&&&&&&& {&&&&&&&&&&&&& &&&&&& case OPND:&&&&&&&&&&&&&&&&&&&& &&&&&& temp.LastInsert(*p); p = Next();&&&&&&&&&&&&& &&&&&& case OPTR:&&&&&&&&&&&&&&&&&&&& &&&&&& while (isp(s.GetTop()) & icp(p-&optr) )&&&&&&&&&&&&&&&&&&&& &&&&&& {&&&&&&&&&&&&&&&&&&&& &&&&&& &&&&&& ExpNode&Type& newoptr(s.Pop());&&&&&&&&&&&&&&&&&&&& &&&&&& &&&&&& temp.LastInsert(newoptr);&&&&&&&&&&&&&&&&&&&& &&&&&& }&&&&&&&&&&&&&&&&&&&& &&&&&& if (isp(s.GetTop()) == icp(p-&optr) )&&&&&&&&&&&&&&&&&&&& &&&&&& {&&&&&&&&&&&&&&&&&&&& &&&&&& &&&&&& s.Pop(); p =Next();&&&&&&&&&&&&&&&&&&&& &&&&&& }&&&&&&&&&&&&&&&&&&&& &&&&&& s.Push(p-&optr); p = Next();&&&&&&&&&&&&& &&&&&& default:&&&&&&&&&&&&&&&&&&&& }&&&&&&&&&&&&& }&&&&&&&&&&&&& *this =&&&&&& &&&&&& pGetFirst()-&data.type = POSTFIX;&&&&&&&&&&&&& return *&&&&&& }&&&&&&& Type Calculate()&&&&&& {&&&&&& &&&&&& Expression temp = *&&&&&&&&&&&&& if (pGetFirst()-&data.type != POSTFIX) temp.Postfix();&&&&&& &&&&&& Stack&Type& Type left,&&&&&&&&&&&&& for (ExpNode&Type& *p = temp.Next(); p != NULL; p = temp.Next())&&&&&&&&&&&&& {&&&&&&&&&&&&& &&&&&& switch (p-&type)&&&&&&&&&&&&&&&&&&&& {&&&&&&&&&&&&& &&&&&& case OPND:&&&&&&&&&&&&&&&&&&&& &&&&&& s.Push(p-&opnd);&&&&&&&&&&&&& &&&&&& case OPTR:&&&&&&&&&&&&&&&&&&&& &&&&&& right = s.Pop(); left = s.Pop();&&&&&&&&&&&&&&&&&&&& &&&&&& switch (p-&optr)&&&&&&&&&&&&&&&&&&&& &&&&&& {&&&&&&&&&&&&&&&&&&&& &&&&&& case '+': s.Push(left + right);&&&&&&&&&&&&&&&&&&&& &&&&&& case '-': s.Push(left - right);&&&&&&&&&&&&&&&&&&&& &&&&&& case '*': s.Push(left * right);&&&&&&&&&&&&&&&&&&&& &&&&&& case '/': if (right != 0) s.Push(left/right); else return 0;//&&&&&&&&&&&&&&&&&& &&&&&& case '%': if (right != 0) s.Push(left%right); else return 0;//&&&&&&&&&&&&&&&&&& &&&&&& case '^': s.Push(Power(left, right));&&&&&&&&&&&&&&&&&&&& &&&&&& default:&&&&&&&&&&&&&&&&&&&& &&&&&& }&&&&&&&&&&&&& &&&&&& default:&&&&&&&&&&&&&&&&&&&& }&&&&&&&&&&&&& }&&&&&&&&&&&&& return s.Pop();&&&&&& }&private:&&&&&& int isp(char optr)&&&&&& {&&&&&&&&&&&&& switch (optr)&&&&&&&&&&&&& {&&&&&&&&&&&&& case '=': return 0;&&&&&&&&&&&&& case '(': return 1;&&&&&&&&&&&&& case '^': return 7;&&&&&&&&&&&&& case '*': return 5;&&&&&&&&&&&&& case '/': return 5;&&&&&&&&&&&&& case '%': return 5;&&&&&&&&&&&&& case '+': return 3;&&&&&&&&&&&&& case '-': return 3;&&&&&&&&&&&&& case ')': return 8;&&&&&& &&&&&& default: return 0;&&&&&&&&&&&&& }&&&&&& }&&&&&&& int icp(char optr)&&&&&& {&&&&&&&&&&&&& switch (optr)&&&&&&&&&&&&& {&&&&&&&&&&&&& case '=': return 0;&&&&&&&&&&&&& case '(': return 8;&&&&&&&&&&&&& case '^': return 6;&&&&&&&&&&&&& case '*': return 4;&&&&&&&&&&&&& case '/': return 4;&&&&&&&&&&&&& case '%': return 4;&&&&&&&&&&&&& case '+': return 2;&&&&&&&&&&&&& case '-': return 2;&&&&&&&&&&&&& case ')': return 1;&&&&&& &&&&&& default: return 0;&&&&&&&&&&&&& }&&&&&& }&};&#endifll000llCalculate()^Power()lisp()icp()^^9 &}
我要回帖
更多推荐
- ·为啥网狐网站看不了专门看电影的浏览器了？
- ·为什么网电视剧狐影免费观看院看不了电影了？
- ·赵磊周震南CP名和赵磊深情演唱《不得不爱》,你觉得他们唱的怎么样?
- ·行尸走肉系列大熊观影绝命毒师顺序该怎么看？
- ·探乐派代言人为什么要找成毅什么咖位？
- ·geekpwn 官网参赛设备有那些？
- ·金士顿电脑内存条内存条分为单模组和双通道，单模的能组双通道吗？
- ·勇士亮放水灯的意义怎么解决
- ·腾讯手机管家私密空间也使用，为什么看私密相册还要启动腾讯手机管家私密空间，到底要怎么启动管家？想看照片都进不去，折磨啊
- ·怎样打开winwindows7任务栏设置置窗口
- ·如何辨别伯希和冲锋衣怎么样的真假
- ·i3 4150 4160配个B85的'主板玩英雄联盟，能开到中效吗？求大神指点
- ·一般的话现在的玛卡正品玛卡官网好不好的呢
- ·三菱叉三菱汽车车架号查询位置
- ·QQ空间那个瓷肌中国化妆品公司瓷肌是真的吗吗？
- ·种子下载你懂得 在线等 高分悬赏 多多益善txt下载
- ·噢龙车310怎么能把歌唱好有劲
- ·硒蛋白金杞明目方真的假的有效吗
- ·qq被删除的好友qq被好友删除怎么找回回
- ·中缀表达式求值算法值
- ·莫斯科没有眼泪简谱怎么排动作
- ·红妍国际女子会馆信誉度娇妍护理液怎么样样？
- ·Oracle vm virtualbox中文版 安装联想OEM WIN7不能自动激活
- ·微信朋友圈微信怎么设置置
- ·360家庭网络管理下载怎么用
- ·安堤调整型内衣文胸聚拢调整型刚穿有什么反应?
- ·如何跑八百米米前心理活动
- ·如何在微信网页版上看到微信聊天记录备份
- ·领秀城购物中心贵和购物中心一般几点开门啊？
- ·悠悠球玄铁磐龙v烂了怎么修
- ·qq怎么改qq匿名能改名字吗的名字
- ·民资jasonwood款号查询吗143001401
- ·目前来说玛卡真的有效果正品的效果是怎样的呢
- ·阿胶西洋参含片味道什么味道
- ·linux上如何添加默认linux 路由器，是类似于linux 路由器器中的8个 0然后指定下一跳的默认linux 路由器，不是添加默认网关
