主题:(原创)栈的应用(算术表达式求值)
大象踩蚂蚁
[专家分:0] 发布于 2006-04-04 07:56:00
谁有数据结构题集的实习部分答案 给我份做参考啊共享下 有的联系我QQ327489180
自己写了个和大家共享下
认为好用的 给我顶下~~~~~~~~~~~~~~~~~~~~~~~~~~~
#include<stdlib.h>
#include<stdio.h>
#define stack_init_size1 40
#define stack_init_size2 20
#define stackincrement1 40
#define stackincrement2 20
typedef struct{
int *base;
int *top;
int stacksize;
}s_stack;
typedef struct{
char *base;
char *top;
int stacksize;
}f_stack;
static char youxian[7][7]=
{
{'>','>','<','<','<','>','>'},{'>','>','<','<','<','>','>'},
{'>','>','>','>','<','>','>'},{'>','>','>','>','<','>','>'},
{'<','<','<','<','<','=','>'},{'>','>','>','>','>','>','>'},
{'<','<','<','<','<','>','='}
};
int in(char c)
{
switch(c)
{
case '+': return 0;
case '-': return 1;
case '*': return 2;
case '/': return 3;
case '(': return 4;
case ')': return 5;
case '#':return 6;
default:return 9;
}
}
void s_push(s_stack *s,int e)
{
if(s->top-s->base>=s->stacksize)
{
s->base=(int *)realloc(s->base,(s->stacksize+stackincrement1)*sizeof(int));
if(!s->base) exit(0);
s->top=s->base+s->stacksize;
s->stacksize+=stackincrement1;
}
*s->top=e; s->top++;
/*printf("the s_stack has the data:%d\n",*(s->top-1));*/
}
void f_push(f_stack *f,char e)
{
if(f->top-f->base>=f->stacksize)
{
f->base=(char *)realloc(f->base,(f->stacksize+stackincrement2)*sizeof(char));
if(!f->base) exit (0);
f->top=f->base+f->stacksize;
f->stacksize+=stackincrement2;
}
*f->top=e;f->top++;
/* printf("the f_stack has the sign:%c\n",*(f->top-1));*/
}
int s_gettop(s_stack *s)
{
s->top--;
return *s->top;
}
char f_gettop(f_stack *f)
{
f->top--;
return *f->top;
}
char pduan(f_stack *f,char c)
{
int m,n;
char w;
m=in(c);
w=*(f->top-1);
n=in(w);
return youxian[n][m];
}
int yunsuan(int p,char r,int q)
{
switch(r)
{
case '+': return q+p;
case '-': return q-p;
case '*': return q*p;
case '/': return q/p;
}
}
回复列表 (共36个回复)
21 楼
chen2319 [专家分:0] 发布于 2006-05-29 16:09:00
我在写这个题目,但是要求多点
就是还能求次芳和绝对值 楼主 你能想想吗?
22 楼
ziyangzhenren [专家分:50] 发布于 2006-06-07 10:04:00
我也做了一个民航系统
想要的
联系我
QQ:308718905
23 楼
ywkyty [专家分:0] 发布于 2006-06-28 17:28:00
哥们儿:
我太爱你了。我找好久了。谢拉。不过不能演示两个栈的变化情况实有点遗憾。努力哟。
24 楼
yanglei1986 [专家分:0] 发布于 2006-10-25 22:14:00
当输入负数时能不能运算?
25 楼
雨523 [专家分:200] 发布于 2006-11-01 11:22:00
[quote]楼主啊,非常鼓励发原创文章,要是写得更好一些,可以写成小论文的形式,那就更好啦~~
已经加精并收集了~~[/quote]
同意
26 楼
bclover [专家分:0] 发布于 2007-02-04 12:56:00
你是不是抄了书上的东西啊?那个7*7的数组应该不是你想出来的吧!怎么跟我昨天在书上看到的饿一样
27 楼
147258 [专家分:0] 发布于 2007-07-07 15:52:00
小弟初学汇编...请多多指教!!
因为是自学的所以很多的东西都搞不清楚
求;各位高手指点
有意者联系本人QQ361469883
谢谢!!!!!!!!!!
哈哈!!!
28 楼
liangbch [专家分:1270] 发布于 2007-07-09 11:49:00
mark
29 楼
liangbch [专家分:1270] 发布于 2007-07-11 10:08:00
我对表达式求解也很有兴趣,打算写一个基于链表的表达式计算器。
我在网上也看到一些类似的计算器,先列出2个,供大家学习。
1。谢云龙的 超级表达式计算器
2。胡春衡的 算霸计算器,这个表达式计算器功能很强大,具有以下特点
1。可输入2,10,16进制数。
2。表达式中可使用下列运算符
+,-,*,/,%,** 加、减、乘、除、取余(对小数亦有效)、幂
&,|,#,~,>>,<< 位与、位或、位异或、位非、移位
>,<,>=,<=,==,<> 大于,小于,大于等于,小于等于,等于,不等于
&&,||, ^^ 逻辑与,逻辑或
! 非(置于数前时)或 阶乘(置于数后时)
# 取字符
3。支持下列函数
sin(x),cos(x),tan(x),csc(x),sec(x),cot(x) 三角函数
arcsin(x),arccos(x),arctan(x),arccsc(x),arcsec(x),arctan2(x,y) 反三角函数
sinh(x),cosh(x),tanh(x),sech(x),coth(x),csch(x) 双曲函数
asinh(x),acosh(x),atanh(x) 反双曲函数
abs(x) 绝对值
ceil(x),floor(x),int(x),round(x),roundto(x,y),trunc(x) 向上取整,向下取整,四舍五入
ln(x),log2(x),log10(x),logn(n,x),exp(x),power(x, y) e为底的对数,2为底的对数,n为底的对数,10为底的对数,e^x
range(m,n),comb(m,n) 排列,组合
max(x1, x2, ...),min(x1, x2,...),mean(x1, x2,...) 最大值,最小值
rand [0..x-1](x为整数)的随机数
pi π
deg(x),rad(x) 弧度转换为角度,角度转换为弧度
4。可自定义变量
可在表达式中使用变量,如变量未初始化,则初始化为0
例如:
a=3
b=a+a
计算结果为6
5。其他功能,具有统计功能,文件功能。
作者的联系方式:
电话:13786846900
QQ:9821423
EMail: jw2004@qq.com
30 楼
Glock18 [专家分:0] 发布于 2008-02-05 20:37:00
输入一个合法算术表达式(字符串),输出它的值。
例如:输入'1+2*3=',输出7
输入'1+2*(3+4)=',输出15
算法描述:直接求中缀表达式的值
将输入部分存起,再从左至右进行扫描
设置两个栈,一个是数栈(SnStack)另一个是运算符栈(SqStack)
扫描规则:
1.遇到数则将数字转化为相应的数
2.遇到运算符,当运算符的优先级高于栈顶的运算符时进运算符栈,否则将数栈的顶部的2个数弹出以运算符栈栈顶的运算符为规则进行运算
3.结束时,将数栈栈顶的数值返回,既为表达式的值
代码如下:
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<string.h>
#define STACK_INIT_SIZE 30 //栈的初始
#define STACK_INCREACE 10 //栈的增值
#define Null '0'
#define OVERFLOW -2
#define MAXSIZE 100
typedef struct STACKoper{ //运算符栈
char *Stop;
char *Sbase;
int stacksize;
}SqStack;
typedef struct STACKnum{ //数栈
float *Stop;
float *Sbase;
int stacksize;
}SnStack;
int InitStackn(SnStack &S) //初始化数栈
{
S.Sbase=(float *)malloc(STACK_INIT_SIZE*sizeof(float));
if(!S.Sbase)
exit(OVERFLOW);
S.Stop=S.Sbase;
S.stacksize=STACK_INIT_SIZE;
return S.stacksize;
}
int InitStack(SqStack &S)
{
S.Sbase=(char *)malloc(STACK_INIT_SIZE*sizeof(char));
if(!S.Sbase)
exit(OVERFLOW);
S.Stop=S.Sbase;
S.stacksize=STACK_INIT_SIZE;
return S.stacksize;
}
char St_pop(SqStack &S) //出运算符栈
{
if(S.Stop==S.Sbase)
return Null;
return *S.Stop--;
}
float Sn_push(SnStack &S,float num) //入数栈
{
if(S.Stop-S.Sbase>=S.stacksize){
S.Sbase=(float *)realloc(S.Sbase,
(S.stacksize+STACK_INCREACE)*sizeof(float));
S.Stop=S.Sbase+S.stacksize;
S.stacksize+=STACK_INCREACE;
}
*++S.Stop=num;
return num;
}
char St_push(SqStack &S,char num)
{
if(S.Stop-S.Sbase>=S.stacksize){
S.Sbase=(char *)realloc(S.Sbase,
(S.stacksize+STACK_INCREACE)*sizeof(char));
S.Stop=S.Sbase+S.stacksize;
}
*++S.Stop=num;
return num;
}
char St_gettop(SqStack &S) //返回栈首元素
{
if(S.Stop==S.Sbase)
return Null;
return *S.Stop;
}
float Sn_gettop(SnStack &S)
{
if(S.Stop==S.Sbase)
return Null;
return *S.Stop;
}
float Sn_pop(SnStack &S)
{
if(S.Stop==S.Sbase)
return Null;
return *S.Stop--;
}
void St_Reset(SqStack &S)
{
S.Stop=S.Sbase;
}
我来回复