数据结构----栈运用的小例子

2019-04-14 08:20发布

题:输入一个10进制整数,输出16进制。

转化16进制数,首先应该除以基数16,得到的模为转化后的最低位的数,得到的商再除以基数16,再得到模就是下个位的数........以此类推,当商等于0时,停止转化。这样我们很容易想到运用栈的特性先进后出来保存得到模,最后全部打印出来;下面使用顺序栈实现:

#include #include #define N 20 typedef int datatype; typedef struct stack{ datatype data[N]; int top; }sqstack; int main() { int n; scanf("%d",&n); sqstack *s; s = (sqstack *)malloc(sizeof(sqstack)); s -> top =-1; while(n>0) { s -> data[++s->top]=n%16; n= n/16; } while(-1 !=s->top) { if(s -> data[s ->top] > 9) printf("%c",s -> data[s -> top]-10 + 'a'); else printf("%d",s-> data[s -> top]); s -> top --; } puts(""); return 0; }

题:求一个表达式的计算结果

首先要建立2个栈:操作数栈和运算符栈,这里要考虑到运算符的优先级。

规则:1、自左向右扫面表达式,如遇到操作数一律进栈;

2、当遇到运算符时,如果他的优先级比栈顶元素的优先级别高时,就进栈。反之,取出栈顶元素和操作数的栈顶元素进行计算,并将结果存如操作数栈,然后继续。

3、左括号一律进运算符栈,右括号一律不进运算符栈,取出运算符栈栈顶元素和操作数栈顶的两个操作数进行计算,并将结果压入操作数栈,知道取出左括号为止。按照下面的规则,实现代码:

#include #include #include "linkstack.h" #define N 32 int Pri(char op) { switch ( op ) { case '+': case '-': return 1; case '*': case '/': return 2; } return 0; } int Compute(int left, int right, char op) { switch ( op ) { case '+': return left + right; case '-': return left - right; case '*': return left * right; case '/': return left / right; } return 0; } void del_op(linkstack *operand, linkstack *operator, char op) { int left, right; char sign; while (!EmptyLinkstack(operator) && Pri(op) <= Pri(GetTop(operator))) { right = PopLinkstack(operand); left = PopLinkstack(operand); sign = PopLinkstack(operator); PushLinkstack(operand, Compute(left, right, sign)); } PushLinkstack(operator, op); return; } int main() { char str[N], *p = str, sign; int sum = 0, left, right; linkstack *operand, *operator; operand = CreateLinkstack(); operator = CreateLinkstack(); scanf("%s", str); while (*p != '