安阳工学院
              表达式相等判断
      班    级：09级计算机科学与信息工程院 
     
 
                                            日期：2011/11/26
一．问题描述：
任给两个表达式都满足下面的性质，判断它们是否相等。
（1）表达式只可能包含一个变量“a”。
（2）表达式中出现的数据都是正整数，而且都小于10000。
（3）表达式中可以包括4种运算“+”，“-”，“*”，“^”以及小括号“（”,“）”小括号的优先级最高，其次是“^”，然后是“*”，最后是“+”和“-”。“+”和“-”的优先级是相同的。相同优先级的运算从左到右进行。
（4）幂指数只可能是1到10之间的正整数。
（5）表达式内部，头部或者尾部都可能有一些多余的空格。
      下面是一些合理的表达式的例子：
（（a^1）^2）^3    a*a+a-a    ((a+a))    9999+(a-a)*a 
1+(a-1)^3        1^10^9
二．问题分析
以字符序列的形式从终端输入语法正确的整数表达式，利用给定的运算符优先关系，实现对表达式的求值。在求值的过程中运算符栈，操作数栈，输入字符和主要操作。
表达式相等判断首先要对表达式处理就要先申请空间利用栈的性质来存储表达式然后建立函数用运算符栈和运算数栈的存取功能和运算符的优先级功能来求表达式的值。
三．数据结构设计
 
四．算法设计
（1）先确定算数表达式求值的运算符优先算法。
（2） 设OPTR和OPND分别为运算符栈和运算数栈，OPSET为运算符集合。
（3）先将数组制空，再将单个数连接到数组中形成字符串。
（4）如果遇到运算符则将字符串数组转化成实数，入栈并重新制空。
（5）不是运算符则进栈，栈顶元素优先权低，脱括号并接受下一字符，退栈并将结果入栈。
五．程序设计
#include <stdio.h>
#include <stdlib.h>
#include<Math.h>
#include <string.h>
#define  error 0
#define  ok  1
#define  overflow  -1
#define STACK_INIT_SIZE  100
switch case判断字符串#define STACKINCREMENT 10
#define OPSETSIZE  7
char OPSET[OPSETSIZE]={'+','-','*','^','(',')','#'};
unsigned char Prior[7][7] = {    //  运算符间的优先关系
        '>','>','<','<','<','>','>',
      '>','>','<','<','<','>','>',
      '>','>','>','<','<','>','>',
      '>','>','>','>','<','>','>',   
      '<','<','<','<','<','=',' ',
      '>','>','>','>',' ','>','>',
      '<','<','<','<','<',' ','='
};       
typedef int Status;
template <typename T>
struct SqStack
{
    T  *top;
    T  *base;
    int  stacksize;
};//顺序栈结构模板
template <typename T1,typename T2>
Status InitStack(T1 &S)
{
    S.base=(T2 *)malloc(STACK_INIT_SIZE*sizeof(T2));
    if(!S.base)  exit (overflow);
    S.top=S.base;
    S.stacksize=STACK_INIT_SIZE;
    return ok;
}//初始化栈函数模板

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。