数据结构表达式求值问题

码拜

8年 ago

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define STACK_INIT_SIZE 20
#define STACKINCREMENT 10
#define ERROR 0
#define OK 1
typedef int ElemType;
typedef struct
{
	ElemType *base;
	ElemType *top;
	int stacksize;
}SqStack;
int InitStack(SqStack *s)
{
	s->base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));
	if(!s->base)
		return ERROR;
	s->top=s->base;
	s->stacksize=STACK_INIT_SIZE;
	return OK;
}
int Push(SqStack *s,char e)
{
	if(s->top-s->base>=s->stacksize)
	{
		s->base=(ElemType *)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(ElemType));
		if(!s->base)
			return ERROR;
		s->top=s->base+s->stacksize;
		s->stacksize+=STACKINCREMENT;
	}
	*(s->top)=e;
	s->top++;
	return OK;
}
int Pop(SqStack *s,char *e)
{
	if(s->top==s->base)
	{
		return ERROR;
	}
	*e=*--(s->top);
	return OK;
}
char GetTop(SqStack s)
{
	if(s.top==s.base)
	{
		return ERROR;
	}
	else
	{
		return (*(s.top-1));
	}
}
int In(char c)//判断c能否为操作符
{
	switch(c)
	{
	case "+":
	case "-":
	case "*":
	case "/":
	case "(":
	case ")":
	case "#":
		return OK;
		break;
	default:return ERROR;
	}
}
char Priority(char t1,char t2)
{
	char f;
	switch(t2)
	{
	case "+":
	case "-":if(t1=="("||t1=="#")
				 f="<";
		else
			f=">";
		break;
	case "*":
	case "/":if(t1=="*"||t1=="/"||t1==")")
				 f=">";
		else
			f="<";
		break;
	case "(":if(t1==")")
				 return ERROR;
		else
			f="<";
		break;
	case ")":switch(t1)
			 {
	case "(":f="=";
		break;
	case "#":return ERROR;break;
	default:f=">";
			 }
	case "#":switch(t1)
			 {
	case "#":f="=";break;
	case "(":return ERROR;break;
	default:f=">";
			 }
	}
	return f;
}
int operate(int a,char theta,int b)
{
	int c;
	switch(theta)
	{
	case "+":
		c=a+b;
		break;
	case "-":
		c=a-b;
		break;
	case "*":
		c=a*b;
		break;
	case "/":
		c=a/b;
		break;
	}
	return c;
}
char final()
{
	SqStack OPTR,OPND;
	char c,x,a,b;
	int i,j,e;
	InitStack(&OPTR);
	Push(&OPTR,"#");
	InitStack(&OPND);
	printf("请输入表达式\n");
	c=getchar();
	while(c!="#"||GetTop(OPTR)!="#")
	{
		if(!In(c))
		{
			Push(&OPND,c);
			c=getchar();
		}
		else
		{
			switch(Priority(GetTop(OPTR),c))
			{
			case "<":Push(&OPTR,c);c=getchar();
				break;
			case "=":Pop(&OPTR,&x);c=getchar();
				break;
			case ">":Pop(&OPTR,&x);Pop(&OPND,&a);Pop(&OPND,&b);
				i=atoi(&a);j=atoi(&b);
				e=operate(j,x,i);
				itoa(e,&a,10);
				Push(&OPND,a);
				break;
			}
		}
	}
	return (GetTop(OPND));
}
int main()
{
	char a;
	a=final();
	printf("%c",a);
	printf("\n");
}

为什么结果不对呢？程序哪里出错了？

解决方案

整数除法 5 / 4 = 1

case “)”:switch(t1)
没有break

代码功能归根结底不是别人帮本人看或讲解或注释出来的；而是被本人静下心来花足够长的时间和精力亲自动手单步或设断点或对执行到某步获得的中间结果显示或写到日志文件中一步一步分析出来的。
提醒：再牛×的老师也无法代替学生本人领悟和上厕所！
单步调试和设断点调试（VS IDE中编译连接通过以后，按F10或F11键单步执行，按Shift+F11退出当前函数；在某行按F9设断点后按F5执行停在该断点处。）是程序员必须掌握的技能之一。

引用:

Quote: 引用:
case “)”:switch(t1)
没有break

最后一个没有break也行吧！

本人说的是倒数第２个，最后一个是case “#”:switch(t1)

i=atoi(&a);j=atoi(&b);
atoi需要的是以”\0″结尾的字符串，而不是一个字符
一个字符的话直接用 a – “0” 得到对应的数值

仅供参考：

/*--
函数型计算器(VC++6.0,Win32 Console)
功能：
目前提供了10多个常用数学函数:
    ⑴正弦sin
    ⑵余弦cos
    ⑶正切tan
    ⑷开平方sqrt
    ⑸反正弦arcsin
    ⑹反余弦arccos
    ⑺反正切arctan
    ⑻常用对数lg
    ⑼自然对数ln
    ⑽ｅ指数exp
    ⑾乘幂函数^
    ⑿向上取整ceil
    ⒀向下取整floor
    ⒁四舍五入取整round
用法：
假如要求2的32次幂，可以打入2^32<回车>
假如要求30度角的正切可键入tan(Pi/6)<回车>
注意不能打入：tan(30)<Enter>
假如要求1.23弧度的正弦，有几种方法都有效：
sin(1.23)<Enter>
sin 1.23 <Enter>
sin1.23  <Enter>
假如验证正余弦的平方和公式,可打入sin(1.23)^2+cos(1.23)^2 <Enter>或sin1.23^2+cos1.23^2 <Enter>
此外两函数表达式连在一起,自动理解为相乘如：sin1.23cos0.77+cos1.23sin0.77就等价于sin(1.23)*cos(0.77)+cos(1.23)*sin(0.77)
当然你还可以依据三角变换，再用sin(1.23+0.77)也即sin2验证一下。
本计算器充分考虑了运算符的优先级因此诸如：2+3*4^2 实际上相当于：2+(3*(4*4))
另外函数名前面假如是数字,那么自动认为二者相乘.
同理，假如某数的右侧是左括号，则自动认为该数与括弧项之间隐含一乘号。
如：3sin1.2^2+5cos2.1^2 相当于3*sin2(1.2)+5*cos2(2.1)
又如：4(3-2(sqrt5-1)+ln2)+lg5 相当于4*(3-2*(√5 -1)+loge(2))+log10(5)
此外，本计算器提供了圆周率 Pi键入字母时不区分大小写,以方便使用。
--*/
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <stdio.h>
#include <string.h>
#include <windows.h>
using namespace std;
const char Tab=0x9;
const int  DIGIT=1;
const int MAXLEN=16384;
char s[MAXLEN],*endss;
int pcs=15;
double round(double dVal, short iPlaces) {//iPlaces>=0
    char s[30];
    double dRetval;
    sprintf(s,"%.*lf",iPlaces,dVal);
    sscanf(s,"%lf",&dRetval);
    return (dRetval);
}
double fun(double x,char op[],int *iop) {
    while (op[*iop-1]<32) //本行使得函数嵌套调用时不必加括号,如 arc sin(sin(1.234)) 只需键入arc sin sin 1.234<Enter>
        switch (op[*iop-1]) {
        case  7: x=sin(x);    (*iop)--;break;
        case  8: x=cos(x);    (*iop)--;break;
        case  9: x=tan(x);    (*iop)--;break;
        case 10: x=sqrt(x);   (*iop)--;break;
        case 11: x=asin(x);   (*iop)--;break;
        case 12: x=acos(x);   (*iop)--;break;
        case 13: x=atan(x);   (*iop)--;break;
        case 14: x=log10(x);  (*iop)--;break;
        case 15: x=log(x);    (*iop)--;break;
        case 16: x=exp(x);    (*iop)--;break;
        case 17: x=ceil(x);   (*iop)--;break;
        case 18: x=floor(x);  (*iop)--;break;
        case 19: x=round(x,0);(*iop)--;break;
        }
    return x;
}
double calc(char *expr,char **addr) {
    static int deep; //递归深度
    static char *fname[]={"sin","cos","tan","sqrt","arcsin","arccos","arctan","lg","ln","exp","ceil","floor","round",NULL};
    double ST[10]={0.0}; //数字栈
    char op[10]={"+"}; //运算符栈
    char c,*rexp,*pp,*pf;
    int ist=1,iop=1,last,i;
    if (!deep) {
        pp=pf=expr;
        do {
            c = *pp++;
            if (c!=" "&& c!=Tab)
                *pf++ = c;
        } while (c!="\0");
    }
    pp=expr;
    if ((c=*pp)=="-"||c=="+") {
        op[0] = c;
        pp++;
    }
    last = !DIGIT;
    while ((c=*pp)!="\0") {
        if (c=="(") {//左圆括弧
            deep++;
            ST[ist++]=calc(++pp,addr);
            deep--;
            ST[ist-1]=fun(ST[ist-1],op,&iop);
            pp = *addr;
            last = DIGIT;
            if (*pp == "("||isalpha(*pp) && strnicmp(pp,"Pi",2)) {//目的是：当右圆括弧的右恻为左圆括弧或函数名字时，默认其为乘法
                op[iop++]="*";
                last = !DIGIT;
                c = op[--iop];
                goto operate ;
            }
        }
        else if (c==")") {//右圆括弧
            pp++;
            break;
        } else if (isalpha(c)) {
            if (!strnicmp(pp,"Pi",2)) {
                if (last==DIGIT) {
                    cout<< "π左侧遇）" <<endl;exit(1);
                }
                ST[ist++]=3.14159265358979323846264338328;
                ST[ist-1]=fun(ST[ist-1],op,&iop);
                pp += 2;
                last = DIGIT;
                if (!strnicmp(pp,"Pi",2)) {
                    cout<< "两个π相连" <<endl;exit(2);
                }
                if (*pp=="(") {
                    cout<< "π右侧遇（" <<endl;exit(3);
                }
            } else {
                for (i=0; (pf=fname[i])!=NULL; i++)
                    if (!strnicmp(pp,pf,strlen(pf))) break;
                if (pf!=NULL) {
                    op[iop++] = 07+i;
                    pp += strlen(pf);
                } else {
                    cout<< "陌生函数名" <<endl;exit(4);
                }
            }
        } else if (c=="+"||c=="-"||c=="*"||c=="/"||c=="%"||c=="^") {
            char cc;
            if (last != DIGIT) {
                cout<< "运算符粘连" <<endl;exit(5);
            }
            pp++;
            if (c=="+"||c=="-") {
                do {
                    cc = op[--iop];
                    --ist;
                    switch (cc) {
                    case "+":  ST[ist-1] += ST[ist];break;
                    case "-":  ST[ist-1] -= ST[ist];break;
                    case "*":  ST[ist-1] *= ST[ist];break;
                    case "/":  ST[ist-1] /= ST[ist];break;
                    case "%":  ST[ist-1] = fmod(ST[ist-1],ST[ist]);break;
                    case "^":  ST[ist-1] = pow(ST[ist-1],ST[ist]);break;
                    }
                } while (iop);
                op[iop++] = c;
            } else if (c=="*"||c=="/"||c=="%") {
operate:        cc = op[iop-1];
                if (cc=="+"||cc=="-") {
                    op[iop++] = c;
                } else {
                    --ist;
                    op[iop-1] = c;
                    switch (cc) {
                    case "*":  ST[ist-1] *= ST[ist];break;
                    case "/":  ST[ist-1] /= ST[ist];break;
                    case "%":  ST[ist-1] = fmod(ST[ist-1],ST[ist]);break;
                    case "^":  ST[ist-1] = pow(ST[ist-1],ST[ist]);break;
                    }
                }
            } else {
                cc = op[iop-1];
                if (cc=="^") {
                    cout<< "乘幂符连用" <<endl;exit(6);
                }
                op[iop++] = c;
            }
            last = !DIGIT;
        } else {
            if (last == DIGIT) {
                cout<< "两数字粘连" <<endl;exit(7);
            }
            ST[ist++]=strtod(pp,&rexp);
            ST[ist-1]=fun(ST[ist-1],op,&iop);
            if (pp == rexp) {
                cout<< "非法字符" <<endl;exit(8);
            }
            pp = rexp;
            last = DIGIT;
            if (*pp == "("||isalpha(*pp)) {
                op[iop++]="*";
                last = !DIGIT;
                c = op[--iop];
                goto operate ;
            }
        }
    }
    *addr=pp;
    if (iop>=ist) {
        cout<< "表达式有误" <<endl;exit(9);
    }
    while (iop) {
        --ist;
        switch (op[--iop]) {
        case "+":  ST[ist-1] += ST[ist];break;
        case "-":  ST[ist-1] -= ST[ist];break;
        case "*":  ST[ist-1] *= ST[ist];break;
        case "/":  ST[ist-1] /= ST[ist];break;
        case "%":  ST[ist-1] = fmod(ST[ist-1],ST[ist]);break;
        case "^":  ST[ist-1] = pow(ST[ist-1],ST[ist]);break;
        }
    }
    return ST[0];
}
int main(int argc,char **argv) {
    int a;
    if (argc<2) {
        if (GetConsoleOutputCP()!=936) system("chcp 936>NUL");//中文代码页
        cout << "计算函数表达式的值。"<<endl<<"支持(),+,-,*,/,%,^,Pi,sin,cos,tan,sqrt,arcsin,arccos,arctan,lg,ln,exp,ceil,floor,round"<<endl;
        while (1) {
            cout << "请输入表达式：";
            gets(s);
            if (s[0]==0) break;//
            cout << s <<"=";
            cout << setprecision(15) << calc(s,&endss) << endl;
        }
    } else if (argc==2 && 0==strcmp(argv[1],"/?")) {
        if (GetConsoleOutputCP()!=936) system("chcp 936>NUL");//中文代码页
        cout << "计算由≥1个命令行参数给出的函数表达式的值。最后一个参数是.0～.15表示将计算结果保留小数0～15位"<<endl<<"支持(),+,-,*,/,%,^^,Pi,sin,cos,tan,sqrt,arcsin,arccos,arctan,lg,ln,exp,ceil,floor,round"<<endl;
    } else {
        strncpy(s,argv[1],MAXLEN-1);s[MAXLEN-1]=0;
        if (argc>2) {
            for (a=2;a<argc-1;a++) strncat(s,argv[a],MAXLEN-1);//将空格间隔的各参数连接到s
            if (1==sscanf(argv[a],".%d",&pcs) && 0<=pcs && pcs<=15) {//最后一个参数是.0～.15表示将计算结果保留小数0～15位
                printf("%.*lf\n",pcs,calc(s,&endss));
            } else {
                strncat(s,argv[a],MAXLEN-1);
                printf("%.15lg\n",calc(s,&endss));
            }
        } else {
            printf("%.15lg\n",calc(s,&endss));
        }
    }
    return 0;
}

题主没注意到操作数及中间结果只能为1位数吗

题主是从http://www.cnblogs.com/Jason-Damon/archive/2011/10/09/2203173.html抄来的吧

引用:

Quote: 引用:
题主是从http://www.cnblogs.com/Jason-Damon/archive/2011/10/09/2203173.html抄来的吧

本人去这怎么长得这么像啊这是我们老师给的代码，难怪问他，他也不知道怎么改、、、

你们老师太水了，你还是要多逛逛csdn

先按9楼说的改了，假如有问题，再发你改好的代码上来

引用:

Quote: 引用:

先按9楼说的改了，假如有问题，再发你改好的代码上来

引用:

先按9楼说的改了，假如有问题，再发你改好的代码上来

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define ERROR 0
#define OK 1
typedef int ElemType;
typedef struct
{
	ElemType *base;
	ElemType *top;
	int stacksize;
}SqStack;
int InitStack(SqStack *s)
{
	s->base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));
	if(!s->base)
		return ERROR;
	s->top=s->base;
	s->stacksize=STACK_INIT_SIZE;
	return OK;
}
int Push(SqStack *s,char e)
{
	if(s->top-s->base>=s->stacksize)
	{
		s->base=(ElemType *)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(ElemType));
		if(!s->base)
			return ERROR;
		s->top=s->base+s->stacksize;
		s->stacksize+=STACKINCREMENT;
	}
	*(s->top)=e;
	s->top++;
	return OK;
}
int Pop(SqStack *s,char *e)
{
	if(s->top==s->base)
	{
		return ERROR;
	}
	*e=*--(s->top);
	return OK;
}
char GetTop(SqStack s)
{
	if(s.top==s.base)
	{
		return ERROR;
	}
	else
	{
		return (*(s.top-1));
	}
}
int In(char c)//判断c能否为操作符
{
	switch(c)
	{
	case "+":
	case "-":
	case "*":
	case "/":
	case "(":
	case ")":
	case "#":
		return OK;
		break;
	default:return ERROR;
	}
}
char Priority(char t1,char t2)
{
	char f;
	switch(t2)
	{
	case "+":
	case "-":if(t1=="("||t1=="#")
				 f="<";
		else
			f=">";
		break;
	case "*":
	case "/":if(t1=="*"||t1=="/"||t1==")")
				 f=">";
		else
			f="<";
		break;
	case "(":if(t1==")")
				 return ERROR;
		else
			f="<";
		break;
	case ")":switch(t1)
			 {
	case "(":f="=";
		break;
	case "#":return ERROR;break;
	default:f=">";
			 }
	case "#":switch(t1)
			 {
	case "#":f="=";break;
	case "(":return ERROR;break;
	default:f=">";
			 }
	}
	return f;
}
int operate(int a,char theta,int b)
{
	int c;
	switch(theta)
	{
	case "+":
		c=a+b;
		break;
	case "-":
		c=a-b;
		break;
	case "*":
		c=a*b;
		break;
	case "/":
		c=a/b;
		break;
	}
	return c;
}
int final()
{
	SqStack OPTR,OPND;
	char x,a,b,c,*str;
	int v,i=0,temp;
	InitStack(&OPTR);
	Push(&OPTR,"#");
	InitStack(&OPND);
	printf("请输入表达式\n");
	str =(char *)malloc(100*sizeof(char));
    gets(str);
    c=str[i];
    i++;
	while(c!="#"||GetTop(OPTR)!="#")
	{
		if(!In(c))
		{
			temp=c-"0";    /*将字符转换为十进制数*/  
            c=str[i];  
            i++;
			while(!In(c))
			{  
				temp=temp*10+c-"0"; /*将逐个读入运算数的各位转化为十进制数*/  
                c=str[i];  
                i++;  
			}  
	    	Push(&OPND,temp);
		}
		else
		{
			switch(Priority(GetTop(OPTR),c))
			{
			case "<":Push(&OPTR,c);c=str[i];i++;
				break;
			case "=":Pop(&OPTR,&x);c=str[i];i++;
				break;
			case ">":Pop(&OPTR,&x);Pop(&OPND,&a);Pop(&OPND,&b);
				v=operate(b,x,a);
				Push(&OPND,v);
				break;
			}
		}
	}
	return (GetTop(OPND));
}
int main()
{
	int a;
	a=final();
	printf("%d",a);
	printf("\n");
}

本人参考了耿国华老师的《数据结构》，本人对着上面的改了一下，还是有一些问题，但是结果能运行对。

可以忽略那个警告，他意思是你Push(&OPND,temp); 参数从int转为char有可能数据丢失