【数据结构算法】栈（三）：逆波兰表达式

分手后的思念是犯贱 2022-05-21 02:15 201阅读 0赞

### 逆波兰表达式 ###

（1-2）*（4+5）转换为逆波兰表达式：1 2 - 4 5 +* ，这种方式对于计算机来说是容易接受的。只需要利用栈的特点，就可以将这种后缀表达式的性能发挥到极致。

### 利用栈求解逆波兰表达式示意图 ###

*  计算逆波兰表达式：1 2 - 4 5 + \*
 *  数字1，2入栈，遇到减号运算符则弹出两个元素进行计算，计算结果入栈
 *  数字4，5入栈，遇到加号运算符则弹出两个元素进行计算，计算结果入栈
 *  最后遇到乘法运算符，将9和-1弹出栈进行乘法计算，此时栈空并无数据压如栈，-9为最终的计算结果。  
    ![这里写图片描述][70]  
    ![这里写图片描述][70 1]  
    ![这里写图片描述][70 2]

### 实现逆波兰计算器 ###

*  实现对逆波兰输入的表达式进行计算
 *  支持带小数点的数据
 *  逆波兰表达式例子：  
    
    
    1.  a+b —> a b +
    2.  a+(b-c)—> a b c - +
    3.  a+(b-c)*d—> a b c - d*  \+

#include<stdio.h> #include<stdlib.h> #include<math.h> #include<iostream> using namespace std; #define STACK_INIT_SIZE 20 #define STACKINCREMENT 10 #define MAXBUFFER 10 typedef double ElemType; typedef struct { ElemType *base; ElemType *top; int stackSize; }sqStack; //初始化栈 void InitStack(sqStack *s) { s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType)); if (!s->base) { exit(0); } s->top = s->base; s->stackSize = STACK_INIT_SIZE; } //压如栈 void Push(sqStack *s, ElemType e) { if (s->top - s->base >= s->stackSize) { s->base = (ElemType *)realloc(s->base, (s->stackSize + STACKINCREMENT)*sizeof(ElemType)); if (!s->base) { exit(0); } } *(s->top) = e; s->top++; } //出栈 void Pop(sqStack *s, ElemType *e) { if (s->top == s->base) { return; } *e = *--(s->top); } //求栈中还有的元素个数 int StackLen(sqStack s) { return (s.top - s.base); } int main() { char c; sqStack s; char str[MAXBUFFER]; double d,e; int i = 0; InitStack(&s); cout<<"请将逆波兰表达式输入各个字符之间用空格隔开，最后用#表示输入结束：\n"; cin>>c; //printf(); //scanf("%c",&c); while (c != '#') { while(isdigit(c) || c=='.')//用于过滤数字,设置缓存区 { str[i++] = c; str[i] = '\0'; if(i>=10) { cout<<"输入数据过大！\n"; //printf("输入数据过大！\n"); return -1; } cin>>c; //scanf("%c",&c); if(c == ' ') { d = atof(str);//将字符串转化为数字 cout<<d; Push(&s, d); i = 0; break; } } switch(c) { case '+': Pop(&s, &e); Pop(&s, &d); Push(&s, e+d); break; case '-': Pop(&s, &e); Pop(&s, &d); Push(&s, e-d); break; case '*': Pop(&s, &e); Pop(&s, &d); Push(&s, e*d); break; case '/': Pop(&s, &e); Pop(&s, &d); if (e!=0) { Push(&s, e/d); } else { cout<<"出错，除数为0!\n"; //printf("出错，除数为0!\n"); return -1; } break; } cin>>c; } Pop(&s, &d); cout<<"最终的计算结果为：\n"<<d<<endl; //printf("最终的计算结果为：%f\n",d); return 0; }

[70]: /images/20220521/baae02bd16fe495f8a8bc80c26f6cecd.png
[70 1]: /images/20220521/07001d9e816a4616898944325c2e0e7e.png
[70 2]: /images/20220521/5a7cd185dfc64c8fa3b85fcaab158f96.png