表达式求值（原创） — 编程爱好者社区

主题：表达式求值（原创）

hoodbar [专家分：0] 发布于 2006-12-13 20:00:00

#include <stdio.h>
#include <conio.h>
#include <malloc.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;

#define STACK_INIT_SIZE 100  //初始分配量
#define STACKINCREMENT 10    //存储空间的分配增量

typedef char ElemType;
typedef ElemType OperandType;   //操作数
typedef char OperatorType;

typedef struct
{
ElemType *base;
ElemType *top;
int stacksize;
}SqStack;

Status InitStack(SqStack &S)
{
//构造一个空栈S
    S.base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
    if(!S.base) exit (OVERFLOW);
S.top = S.base;
    S.stacksize = STACK_INIT_SIZE;
    return OK;
}

Status GetTop(SqStack S){
ElemType e;
if (S.top == S.base) return ERROR;
e = *(S.top-1);
return e;
}

Status Push (SqStack &S,ElemType e)
{
//插入元素e为新的栈顶元素
if (S.top - S.base >= S.stacksize){
  S.base = (ElemType *) realloc ( S.base,
   (S.stacksize + STACKINCREMENT) * sizeof(ElemType));
  if(!S.base) exit (OVERFLOW);
  S.top = S.base + S.stacksize;
  S.stacksize += STACKINCREMENT;
}
*S.top++ = e;
return OK;
}

Status Pop (SqStack &S,ElemType &e){
//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
    if(S.top == S.base) return ERROR;
    e = * --S.top;
    return OK;
}

char In(char c,char OP[])
{
if(c>=35 && c<=47)
  return 1;
else return 0;
}

char OP[8]={'+','-','*','/','(',')','#','\0'};
int m[7][7]={1,1,2,2,2,1,1,

       1,1,2,2,2,1,1,

    1,1,1,1,2,1,1,
    1,1,1,1,2,1,1,
    2,2,2,2,2,0,-1,
    1,1,1,1,-1,1,1,
    2,2,2,2,2,-1,0};//1 >  2 <  0 =  -1 不存在

char Precede(char i,char j)
{
int a,b; char *p;
for(p=OP,a=0;*p!='\0';p++,a++)
  if(*p==i) break;
for(p=OP,b=0;*p!='\0';p++,b++)
  if(*p==j) break;
  if(m[a][b]==1) return '>';
  else if(m[a][b]==2) return '<';
  else if(m[a][b]==0) return '=';
  else return 'O';
}

char Operate(char a,char theta,char b)
{
if(a>47) a=atoi(&a);
if(b>47) b=atoi(&b);
switch(theta)
{
case '+': return a+b;
    break;
case '-': return a-b;
   break;
case '*': return a*b;
   break;
case '/': return a/b;
   break;
}
}

OperandType EvaluateExpression()
{
SqStack OPTR,OPND;
OperandType a,b,c; OperatorType theta;
InitStack(OPTR); Push(OPTR,'#');
InitStack(OPND); c=getchar();
while (c!='#' || GetTop(OPTR)!='#')
{
  if (!In(c,OP)){Push(OPND,c);c=getchar();}
  else
   switch(Precede(GetTop(OPTR),c))
  {
   case '<' :
    Push(OPTR,c); c = getchar();
    break;
   case '=' :
    Pop(OPTR,c); c = getchar();
    break;
   case '>' :
    Pop(OPTR,theta);
    Pop(OPND,b); Pop(OPND,a);
    Push(OPND,Operate(a,theta,b));
    break;
  }
}
return GetTop(OPND);
}

void main()
{
printf("(以#为结束符)\n");
printf("请输入：\n");
int a;
a=(int)EvaluateExpression();
printf("%d",a);
getch();
}

本帖地址： http://bbs.pfan.cn/post/209345.html

回复列表（共21个回复）

沙发

hoodbar [专家分：0] 发布于 2006-12-13 20:04:00

此程序是我们的一次作业，由于输入的是字符形式，所以不能输入大于10的数，在VC6.0上编译通过。望大家指教。

板凳

freeeerf [专家分：5440] 发布于 2006-12-13 23:33:00

好,有前途!
建议把void main()
改成int main()
后面再加一个return 0; //这是那个什么标准.
就更好了.

3 楼

hqin6 [专家分：140] 发布于 2006-12-14 15:23:00

我也写了一个：

4 楼

hqin6 [专家分：140] 发布于 2006-12-14 15:24:00

第一个头文件：
debug.h
**************
class NoMen         //异常类
{
public:
    NoMen(){}
protected:
private:
};
class OutOfBounds
{
public:
    OutOfBounds(){}
protected:
private:
};

5 楼

hqin6 [专家分：140] 发布于 2006-12-14 15:26:00

第二个头文件：
lei.h
**************
#include <iostream>
#include <string>
#include "Stack.h"
using namespace std;
template<class T>
class MidOrder             //运算符
{
public:
    MidOrder(){}
    ~MidOrder(){}
    void Input(){cin>>str;}
    MidOrder<T>&EraseError();//除去输入中误输入的字符，比如aaa2+3擦去aaa
    bool Count(T x,T y,char sign,T& result);//计算x sign y,结果放入result，sign=+、-、*、/
    T Distribute(); //分配入栈
protected:
private:
    string str;//输入的字符串
    Stack<T> NumStack;//数据栈
    Stack<char> SignStack;//符号栈
};
template<class T>
MidOrder<T>&MidOrder<T>::EraseError()
{
    int len=str.length();
    while ((str[0]<48||str[0]>57)&&str[0]!='-'&&str[0]!='(')
    {
        str.erase(str.begin());//erase---擦去str第一个字符,是系统自带的函数
        if(str.length()==0)break;
    }
    if(str.length()==0)throw OutOfBounds();//对应于输入aaaaaa这种情况
    return *this;
}
(待续)

6 楼

hqin6 [专家分：140] 发布于 2006-12-14 15:26:00

（接上面）
template<class T>
bool MidOrder<T>::Count(T x,T y,char sign,T& result)
{
    switch(sign)
    {
    case '+':result=x+y;
        break;
    case '-':result=x-y;
        break;
    case '*':result=x*y;
        break;
    case '/':if(y==0)throw OutOfBounds();result=x/y;
        break;
//    case '%':result=x%y;         //只有当T是int才用这行
    //    break;
    default: return false;
        break;
    }
    return true;
}
int PRI(char sign)//计算sign的优先级
{
    if (sign=='*'||sign=='/'||sign=='%')return 2;
    if(sign=='+'||sign=='-')return 1;
    return 0;
}
template<class T>
T MidOrder<T>::Distribute()
{
    EraseError();//擦去不正确的输入
    cout<<str<<endl;//输出实际要计算的表达式
    for (int i=0;i<str.length();)
    {
        if (str[i]>47&&str[i]<58||str[i]=='-'&&(i==0||str[i-1]=='('))//读入的是数字。str[i]=='-'&&i==0对应输入的第一个数是负数，str[i]=='-'&&str[i-1]=='('对应的是在表达式中的(-8+9)这种情况
        {
            T num;
            string one_num;
            while (str[i]>47&&str[i]<58||str[i]=='-'&&(i==0||str[i-1]=='(')||str[i]=='.')
            {
                one_num.append(str[i],1);//////////&str[i]
                i++;
            }
            num=atof(&one_num[0]);//系统函数，将字符串one_num转换成一个T型的数
            NumStack.Add(num);
            cout<<"把"<<num<<"压入数据栈!"<<endl;
            continue;
        }
        if (SignStack.IsEmpty()||str[i]=='(')
        {
            SignStack.Add(str[i]);
            i++;
            cout<<"把"<<str[i-1]<<"压入符号栈!"<<endl;
            continue;
        }
        if (str[i]==')')
        {
            char sign;
            while (SignStack.Top()!='(')
            {
                SignStack.Delete(sign);
                cout<<"弹出"<<sign<<"."<<endl;
                T x,y,res;
                NumStack.Delete(x);
                cout<<"弹出"<<x<<"."<<endl;
                NumStack.Delete(y);
                cout<<"弹出"<<y<<"."<<endl;
                Count(y,x,sign,res);
                NumStack.Add(res);
                cout<<"将计算的结果"<<res<<"压入数据栈!"<<endl;
            }
            SignStack.Delete(sign);
            cout<<"将符号"<<sign<<"压入符号栈!"<<endl;
            i++;
            continue;
        }
        if (PRI(str[i])>PRI(SignStack.Top()))
        {
            SignStack.Add(str[i]);
            cout<<"把"<<str[i]<<"压入符号栈!"<<endl;
            i++;
            continue;
        }
        else
        {
            char sign;
            SignStack.Delete(sign);
            cout<<"弹出"<<sign<<"."<<endl;
            T x,y,res;
            NumStack.Delete(x);
            cout<<"弹出"<<x<<"."<<endl;
            NumStack.Delete(y);
            cout<<"弹出"<<y<<"."<<endl;
            Count(y,x,sign,res);
            NumStack.Add(res);
            cout<<"将计算的结果"<<res<<"压入数据栈!"<<endl;
            SignStack.Add(str[i]);
            cout<<"把"<<str[i]<<"压入符号栈!"<<endl;
            i++;
            continue;
        }
    }
    while (!SignStack.IsEmpty())
    {
        char sign;
        SignStack.Delete(sign);
        cout<<"弹出"<<sign<<"."<<endl;
        T x,y,res;
        NumStack.Delete(x);
        cout<<"弹出"<<x<<"."<<endl;
        NumStack.Delete(y);
        cout<<"弹出"<<y<<"."<<endl;
        Count(y,x,sign,res);
        NumStack.Add(res);
        cout<<"将计算的结果"<<res<<"压入数据栈!"<<endl;
    }
    return NumStack.Top();
}

7 楼

hqin6 [专家分：140] 发布于 2006-12-14 15:27:00

第三个头文件：
Stack.h
×××××××××××××××
#include "debug.h"       //全是书上的，一点没改
template <class T>
class Node
{
public:
    T data;
    Node<T> *link;
protected:
private:

};
template<class T>
class Stack             //操作数
{
public:
    Stack(){top=0;}
    ~Stack();
    bool IsEmpty()const{return top==0;}
    bool IsFull()const;
    T Top()const;
    Stack<T>& Add(const T&x);
    Stack<T>&Delete(T&x);
protected:
private:
    Node<T>*top;
};
template<class T>
Stack<T>::~Stack()
{
    Node<T>*next;
    while (top)
    {
        next=top->link;
        delete top;
        top=next;
    }
}
template<class T>
bool Stack<T>::IsFull()const
{
    try
    {
        Node<T> *p=new Node<T>;
        delete p;
        return false;
    }
    catch (NoMen)
    {
        return true;
    }
}
template<class T>
T Stack<T>::Top()const
{
    if(IsEmpty())throw OutOfBounds();
    return top->data;
}
template<class T>
Stack<T>& Stack<T>::Add(const T&x)
{
    Node<T>*p=new Node<T>;
    p->data=x;
    p->link=top;
    top=p;
    return *this;
}
template<class T>
Stack<T>&Stack<T>::Delete(T&x)
{
    if (IsEmpty())throw OutOfBounds();
    x=top->data;
    Node<T>*p=top;
    top=top->link;
    delete p;
    return *this;
}

8 楼

hqin6 [专家分：140] 发布于 2006-12-14 15:28:00

主函数：
main.cpp
*************************
#include <iostream>
#include "lei.h"
using namespace std;//若要计算float型的数，请删掉lei.h中的取余符号%
void main()
{
    try
    {
        MidOrder<float> myMidOrder;
        myMidOrder.Input();
        cout<<"结果是： "<<endl<<myMidOrder.Distribute()<<endl;
    }
    catch (OutOfBounds)
    {
        cout<<"输入有误!"<<endl;
        exit(1);
    }

}

9 楼

hqin6 [专家分：140] 发布于 2006-12-14 15:30:00

当然，还可以用二叉树做，代码我也写了：

10 楼

hqin6 [专家分：140] 发布于 2006-12-14 15:31:00

第一个头文件：
BinaryTreeNode.h
×××××××××××××××
template<class T> class BinaryTree;
template<class T>
class BinaryTreeNode
{
public:
    friend class BinaryTree<T>;
    BinaryTreeNode(){LeftChild=RightChild=0;}
    BinaryTreeNode(const T &e){data=e;LeftChild=RightChild=0;}
    BinaryTreeNode(const signed &s,bool){sign=s;LeftChild=RightChild=0;}
    BinaryTreeNode(const signed&s,BinaryTreeNode*l,BinaryTreeNode*r)
    {
        sign=s;
        LeftChild=l;
        RightChild=r;
    }
protected:
private:
    T data;
    char sign;
    BinaryTreeNode<T>*LeftChild,*RightChild;
};

我来回复

您尚未登录，请登录后再回复。点此登录或注册

主题：表达式求值（原创）

回复列表（共21个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：表达式求值（原创）

回复列表 （共21个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共21个回复）