/*
*链式栈的实现
*/
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define T int
//------链栈的存储结构------
typedef struct{//链结点
T data;
struct Stack *Link;//指向下一个节点
}Stack,*LinkNode;
LinkNode S;
void InitStack()
{//构造空栈,栈顶指针置空,S是链栈的栈顶
S=NULL;
}
bool push(T e)
{//入栈将e插入表头,并使S指向e
Stack* p=(Stack*)malloc(sizeof(Stack));
if(p==NULL)return false;
p->data=e;
p->Link=S;
S=p;
return true;
}
T pop()
{//退栈,用x返回栈顶元素
LinkNode p=S;
T x=S->data;
S=S->Link;
free(p);
return x;
}
T getop()
{//获取栈顶
return S->data;
}
bool IsEmpty()
{//判断栈是否为空,是返回true,否则返回false
if(S==NULL)return true;
else return false;
}
/*bool BracketMatching(char s[],int n)
{//括号匹配
for(int i=0;i<n;i++)
{
if(s[i]=='('||s[i]=='['||s[i]=='{')push(s[i]);
if(s[i]==')')
{
if(!IsEmpty()&&getop()=='(')pop();
else return false;
}
if(s[i]==']')
{
if(!IsEmpty()&&getop()=='[')pop();
else return false;
}
if(s[i]=='}')
{
if(!IsEmpty()&&getop()=='{')pop();
else return false;
}
}
if(IsEmpty())return true;
else return false;
}*/
void ReversePolishCalculator(char ch[],int n)
{//逆波兰表达式计算
T el ,ell; //栈顶el,与el后面的ell
T d=0; //用于累计数字
int i =0; //数组下标
while(i<n)
{
switch(ch[i]){
case '+':
el=pop();
ell=pop();
push(el+ell);
break;
case '*':
el=pop();
ell=pop();
push(el*ell);
break;
case '-':
el=pop();
ell=pop();
push(el-ell);
break;
case '/':
el=pop();
ell=pop();
if(el==0){printf("除0");exit(0);}
push(el/ell);
break;
case ' ':break;
default :
while(ch[i]>='0'&&ch[i]<='9'){
d=d*10+ch[i]-'0';
i++;
}
push(d);
break;
}
i++;
d=0;
}
}
int main()
{
char cht[100];
fgets(cht,100,stdin);
int u=0;
while(cht[u++]!='\n');
ReversePolishCalculator(cht,u-1);
printf("%d",getop());
}
链式栈的实现及部分应用
最后编辑于 :
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
- 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...