跪求数据结构一个关于栈的算法问题 数据结构入栈出栈算法
数据结构中关于栈的问题
主要是考察把中缀表达式换为后缀表达式
然后运用堆栈求值的运算
我可以提供一点思路——供参考
【将中缀表达式转化为后缀】
#include
#include
#include
typedef struct node
{
char data; int code; int pri;
struct node *link;
}NODE;
struct Tb1
{
char data; int code; int pri;
}opchTb1[]={{'*',1,4},{'/',2,4},{'+',3,2},{'-',4,2},{'(',5,5},{')',6,1},{'\0',7,0},{'#',-1,0}};
NODE *optop;
char num[200], *numtop;
char expStr[200];
void push(char x,int c,int p,NODE **toppt)
{
NODE *q=(NODE *)malloc(sizeof(NODE));
q->data=x;
q->code=c;
q->pri=p;
q->link=*toppt;
*toppt=q;
}
int pop(char *op,int *cp, NODE **toppt)
{
NODE *q=*toppt;
if(*toppt==NULL) return 1;
*op=q->data;
*cp=q->code;
*toppt=q->link;
free(q);
return 0;
}
int expr(char *pos)
{
struct Tb1 *op;
char sop;
int type,code,n,m,i,c;
optop=NULL;
numtop=num;
n=m=0;
c=' ';
push('#',0,0,*optop);
while(1){
while(c==' '||c=='\t') c=*pos++;
if(isalpha(c)){
*numtop++=' ';
while(isalpha(c)||isdigit(c)) {*numtop++=c;c=*pos++;}
if(m) return 1;
m=1;
continue;
}
else {
for(i=0;opchTb1[i].code!=-1&&opchTb1[i].data!=c;i++)
if(opchTb1[i].code==-1) return 3;
op=&opchTb1.[i];
type=opchTb1.[i].code;
c=*pos++;
}
if(type<5){
if(m!=1) return 1;
m=0;
}
if(type==5) n++;
if(type==6){
if(n--==0) return 2;
if(op->pri>optop->pri)
if(op->data=='(') push(op->code,1,*optop);
else push(op->data,op->code,op->pri,*optop);
else{
while(optop!=NULL&&op->pri<=optop->pri) {
pop(&sop,&code,&optop);
if(code<5&&code>0) {
*numtop++=' ';
*numtop++=sop;
}
}
if(op->data=='\0') return(n!=0||(m!=1&&numtop>num))?4:(*numtop='\0');
else if(op->data!=')') push(op->data,op->code,op->pri,&optop);
}
}
}
void main()
{
int d;
printf("please input the string!\n");
gets(expStr);
if((d=expr(expStr))==0) printf("the postfix string is:%s\n",num);
else printf("The string error! the error is:%d\n",d);
getch();
}
【后缀表达式的计算】
#include
#include
#include
#define MAXCOLS 80
#define TRUE 1
#define FLASE 0
double eval(char[]);
double pop(struct stack *ps);
void push(struct stack *ps,double x);
int empty(struct stack *ps);
int isdigit(char);
double oper(int,double,double);
void main()
{
char expr[MAXCOLS];
int position=0;
printf("\nPlease input the string:");
while((expr[position++]=getchar())!='\n');
expr[--position]='\0';
printf("%s%s","the original postfix expression is",expr);
printf("\n%f",eval(expr));
getch();
} /*end main*/
/*程序的主要部分eval函数，这个函数只是计算算法的C语言实现，同时考虑了特定的环境和数据的输入*/
/*输出格式。eval调用了一个isdigit函数，它用来判断其参数是不是一个操作数。在函数eval及其调用的*/
/*pop和push例程中都使用了下面的堆栈说明。eval函数在声明后给出*/
struct stack{
int top;
double items[MAXCOLS];
};
double eval(char expr[])
{
int c,position;
double opnd1,opnd2,value;
struct stack opndstk;
opndstk=-1;
for(position=0;(c=expr[position])!='\0';position++)
if(isdigit(c)) /*operand--convert the character representation of the digit into double and*/
/*push it onto the stack*/
push(&opndstk,(double)(c-'0'));
else{ /*operator*/
opnd2=pop(&opndstk);
opnd1=pop(&opndstk);
value=oper(c,opnd1,opnd2);
push(&opndstk,value);
} /*end else*/
return(pop(&opndstk));
}/*end eval*/
/*下面的函数在许多C系统中都被预定义为一个宏*/
int isdigit(char symb)
{
return(symb>='0'&&symb<='9');
}
/*函数oper首先检查它的第一个参数是不是一个合法的运算符，如果是，则用另外两个参数来决定运算结果*/
/*对于求幂运算，使用了math.h中定义的函数pow（op1，op2）。*/
double oper(int symb,double op1,double op2)
{
switch(symb){
case '+' : return(op1+op2);
case '-' : return(op1-op2);
case '*' : return(op1*op2);
case '/' : return(op1/op2);
case '$' : return(pow(op1,op2));
default:printf("%s","illegal operation");
exit(1);
}/*end switch*/
}/*end oper*/
double pop(struct stack *ps)
{
if(empty(ps)){
printf("%s","stack underflow");
exit(1);
} /*end if*/
return(ps->items[ps->top--]);
}/*end pop*/
void push(struct stack *ps,double x)
{
ps->items[++(ps->top)]=x;
return;
} /*end push*/
int empty(struct stack *ps)
{
return(ps->top==-1);
}/*end empty*/
希望对你有帮助
栈的运算问题？
这是PASCAL吧，大学时学的东西，已经忘得差不多了。
PROCEDURE xxx(VAR s:stack): //建立一个过程函数xxx，有一个参数s，类型为栈
BEGIN //函数开始
IF s.t=0 //如果s参数的t属性为0
THEN print('underflow') //打印已经置空了
ELSE s.t:=s.t-1; //否则将t属性-1
END;
数据结构 栈的问题
第一个问题
push函数错了
void push_seq(PSeqStack pastack,Datatype x)//插入元素 X；
{
if(pastack->top==pastack->MAXNUM-1)//判断是否溢出
printf("Owerflow\n");
else
{
pastack->top=pastack->top+1;//将栈顶标记加1；
pastack->s[pastack->top]=x;
}
}
第二个问题
栈有个独立的IsEmpty函数，你已经写了，不过写错了
int isEmptyStack_seq(PSeqStack pastack) //判断栈是否为空；即是否下溢
{
return(pastack->top==-1);
}
对top和pop函数使用之前，应该调用这个函数
int main()
{
PSeqStack p;
p=creatEmptyStack_seq(10);//创建一个空栈！大小为10个DataType
if(!isEmptyStack_seq(p))
printf("%d\n", top_seq(p));
else
printf("It is empty\n");
}
数据结构：利用栈来实现算术表达式求值的算法。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define error 0
#define ok 1
#define overflow -1
#define STACK_INIT_SIZE 100
#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=S.base;
S.stacksize=STACK_INIT_SIZE;
return ok;
}//初始化栈函数模板
template <typename T1,typename T2>
Status Push(T1 &S,T2 e)
{
if(S-S.base>=S.stacksize)
{
S.base=(T2 *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(T2));
if(!S.base) exit (overflow);
S=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S++=e;
return ok;
}//入栈函数模板
template <typename T1,typename T2>
Status Pop(T1 &S,T2 &e)
{
if(S==S.base) return error;
e=*--S;
return ok;
}//出栈函数模板
template <typename T1,typename T2>
T2 GetTop(T1 S)
{
if(S==S.base)
return error;
else
return *(S-1);
}//获取栈顶元素模板
Status In(char Test,char* TestOp) {
bool Find=false;
for (int i=0; i< OPSETSIZE; i++) {
if (Test == TestOp[i]) Find= true;
}
return Find;
}//判断是否为运算符
float Operate(float a,unsigned char theta, float b) {
switch(theta) {
case '+': return a+b;
case '-': return a-b;
case '*': return a*b;
case '/': return a/b;
default : return 0;
}
}//运算
int ReturnOpOrd(char op,char* TestOp) {
int i;
for(i=0; i< OPSETSIZE; i++) {
if (op == TestOp[i]) return i;
}
return 0;
}
char precede(char Aop, char Bop) {
return Prior[ReturnOpOrd(Aop,OPSET)][ReturnOpOrd(Bop,OPSET)];
}//ReturnOpOrd和precede组合，判断运算符优先级
float EvaluateExpression() {
// 算术表达式求值的算符优先算法。
// 设OPTR和OPND分别为运算符栈和运算数栈，OPSET为运算符集合。
SqStack<char> OPTR; // 运算符栈，字符元素
SqStack<float> OPND; // 运算数栈，实数元素
char TempData[20];
float Data,a,b;
char theta,c,x,Dr[2];
InitStack<SqStack<char>,char> (OPTR);
Push (OPTR, '#');
InitStack <SqStack<float>,float>(OPND);
strcpy(TempData,"\0");//将TempData置为空
c=getchar();
while (c!= '#' || GetTop<SqStack<char>,char>(OPTR)!= '#')
{
if (!In(c, OPSET))
{
Dr[0]=c;
Dr[1]='\0';//存放单个数
strcat(TempData,Dr);//将单个数连到TempData中，形成字符串
c=getchar();
if(In(c,OPSET))//如果遇到运算符，则将字符串TempData转换成实数，入栈，
并重新置空
{
Data=(float)atof(TempData);
Push(OPND, Data);
strcpy(TempData,"\0");
}
}
else
{ // 不是运算符则进栈
switch (precede(GetTop<SqStack<char>,char>(OPTR), c)) {
case '<': // 栈顶元素优先权低
Push(OPTR, c);
c=getchar();
break;
case '=': // 脱括号并接收下一字符
Pop(OPTR, x);
c=getchar();
break;
case '>': // 退栈并将运算结果入栈
Pop(OPTR, theta);
Pop(OPND, b);
Pop(OPND, a);
Push(OPND, Operate(a, theta, b));
break;
} // switch
}
} // while
return GetTop<SqStack<float>,float>(OPND);
} // EvaluateExpression
void main()
{
printf("请输入表达式（end #）：\n");
printf("%f\n",EvaluateExpression());
}
给你一个完全的程序，本人自己写的。