首页 > 代码库 > 栈的应用举例-进行算术运算
栈的应用举例-进行算术运算
这个例子是来自于严蔚敏的《数据结构》的栈那一节。 但是我进行了一些简单的修改,确保编译通过。
目的:利用栈 计算 “3*(7-2)”这样的字符串的算术运算的结果。 共有3个代码文件,如下:
1、mystack.h
#pragma once#define maxsize 30typedef struct{ char data[maxsize+1]; int top;}Stack;int Push(Stack& S,char x);int Pop(Stack& S,char& x);char readtop(Stack S);
2、mystack.cpp
#include "mystack.h"#include "stdio.h"int Push(Stack& S,char x){ if (S.top==maxsize) { printf("overflow\n"); return(0); } S.data[++S.top]=x; return(1);}int Pop(Stack& S,char& x){ if(S.top==0) { printf("undertflow\n"); return(0); } x=S.data[S.top]; S.top--; return(1);}char readtop(Stack S){ char a; a=S.data[S.top]; return(a);}
3、 caclstack.cpp
#include <iostream>#include <string>#include "mystack.h"using namespace std;double operate(char ch, double x,double y);int precede(char p1,char p2);double calcul(char a[]);
//这是进行测试的main 函数int main(){ char tmp[]="3*(7-2)#"; // 输入的字符串一定要以# 结尾。 // char tmp[]="3*(7-2)+5*2#"; double rst = calcul(tmp); cout<<rst<<endl; getchar(); return 0;}double operate(char ch, double x,double y){ double z; switch (ch) { case '+' : z=x+y; break; case '-' : z=x-y; break; case '*' : z=x*y; break; case '/' : z=x/y; break; } return((char)z);}//这个函数最关键int precede(char p1,char p2){ int flag = -2; switch (p1) { case '+' : if(p2=='*' || p2=='/' || p2== '(' ) flag=-1; else flag=1; break; case '-' : if(p2=='*' || p2=='/' || p2== '(' ) flag=-1; else flag=1; break; case '*' : if(p2=='(' ) flag=-1; else flag=1; break; case '/' : if(p2=='(' ) flag=-1; else flag=1; break; case '(' : if(p2==')') flag=0; else if(p2=='#')printf("error 1 operator!\n"); else flag=-1; break; case ')' : if(p2=='(' )printf("error 2 operator!\n"); else flag=1; break; case '#' : if(p2==')' )printf("error 3 operator!\n"); else if(p2=='#' ) flag=0; else flag=-1; break; } return(flag);}double calcul(char a[]){ Stack S1, S2; S1.top = 0; S2.top = 0; double x, y, z; char x1,x2; char r, ch; int I=0; Push(S1,'#'); r=a[I]; //while(r<>'#' || readtop(S1)<>'#') while(r != '#' || readtop(S1) != '#') { if(r<='9' && r>='0') { x=0; while(r<='9' && r>='0') { x=x*10+r-'0'; r=a[++I]; } Push(S2,x); } else switch(precede(readtop(S1),r)) { case -1: Push(S1,r); r=a[++I]; break; //把运算符放进栈1 case 0: Pop(S1,ch); r=a[++I]; //r=a[I]; break; //弹出一个运算符 case 1: Pop(S1, ch); Pop(S2, x1); Pop(S2, x2); Push(S2,operate(ch, x2,x1)); //r=a[++I]; r=a[I]; break; } } return(readtop(S2));}
以上代码在VS 下编译通过,并且执行结果正确。
注意:本文的栈 是用的自定义 的mystack。
另外更多原理 请参考 严蔚敏的数据结构相关章节。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。