逆波兰表达式求值（实验报告及C++源码）

数据结构课程实验指导书

逆波兰表达式求值

一、需求分析

1、从键盘中输入一个后缀表达式，该表示包括加减乘除等操作符，以及正整数作为操作数等。

2、用堆栈来实现 3、测试数据 输入：2 3 * 1 – #

输出：2 3 * 1 -- =5

二、概要设计 抽象数据类型

需要一个浮点数栈来存储还没有计算的浮点数或者运算的结果。 ADT Stack

数据成员：int size; int top; //分别用于存储栈大小、栈顶位置

float *listArray;//存储浮点型数字的数组

成员函数： bool push(float it); bool pop(float& it); bool isEmpty(); //判断栈为空 bool isOne();//判断栈是否只有一个元素 算法的基本思想

1. 逐一扫描字符串，用ascii码进行判断，如果该字符是数字，则利用x=x*10+str[i]-48

将数据由字符类型转换为浮点型数据； 2. 如果字符是‘.’，则将‘.’转化为小数点，并将‘.’后的数据转化为小数部分； 3. 遇到空格前是数据的，将x押入栈；

4. 如果该字符是’+’，’-’，’*’或’/’，判断栈里的元素是否少于两个个，如果少于两个，

报错；如果大于等于两个，就弹出两个数据，并进行相应的计算； 程序的流程

输入字符串，程序对字符串依次扫描。扫描一位，处理一位。扫描完成后，判断栈里是不是只有一个数据，若是，得到正确结果；若不是，则表达式出错。 三、详细设计

物理数据类型

用浮点数类型的栈存储运算中要用的数据，需要入栈、出栈，故设计如下的浮点类型的栈：

class Stack {

private: int size; int top; float *listArray; public: Stack(int sz=20); ~Stack();

－ 1 －

数据结构课程实验指导书

bool push(float it);//入栈 bool pop(float& it);//出栈 bool isEmpty();//判断栈是否为空 bool isOne(); //判断栈里是否只有且仅有一个元素 };

成员函数的函数体

return true; Stack::Stack(int sz) //栈构造函数

{ } size=sz; bool Stack::isEmpty() //判断站是否为空 top=0; { listArray=new float[size]; if(top==0) } return true; bool Stack::push(float it) return false; { } if(top==size) bool Stack::isOne() return false; { listArray[top++]=it; if(top==1) return true; return true; } return false; bool Stack::pop(float& it) } { Stack::~Stack() if(top==0) { return false; delete listArray; it=listArray[--top]; }

算法的具体步骤 用switch语句实现 1. 逐一扫描字符串，用ascii码进行判断，如果该字符是数字，则利用x=x*10+str[i]-48

将数据由字符类型转换为浮点型数据； 2. 如果字符是‘.’，则将‘.’转化为小数点，并将‘.’后的数据转化为小数部分； 3. 遇到空格前是数据的，将x押入栈；

4. 如果该字符是’+’，’-’，’*’或’/’，判断栈里的元素是否少于两个个，如果少于两个，

报错；如果大于等于两个，就弹出两个数据，并进行相应的计算； 算法的时空分析

因为入栈、出栈的时间复杂度均为Θ(1)，所以时间的复杂度主要取决于字符串的长度，空间也同样取决于字符串长度。时间复杂度为Θ(n)。

输入和输出的格式 输入：2 3 * 1 – #

输出：2 3 * 1 -- =5

五、测试结果

－ 2 －

数据结构课程实验指导书

六、用户使用说明（可选）

1. 运行程序后，直接输入后缀表达式；

2. 用户输入的表达式必须符合后缀表达式的要求，并以‘#’号结束。 七、附录（可选） #include it=listArray[--top]; #include return true; using namespace std; } class Stack bool Stack::isEmpty() //判断站是否为空 { { private: if(top==0) int size; return true; int top; return false; float *listArray; } public: bool Stack::isOne() Stack(int sz=20); { ~Stack(); if(top==1)

return true; bool push(float it);//入栈

return false; bool pop(float& it);//出栈

} bool isEmpty();//判断栈是否为空

Stack::~Stack() bool isOne();//判断栈里是否一个元素

}; {

delete listArray; Stack::Stack(int sz) //栈构造函数

{ } size=sz; //此函数传进输入的字符串，并对字符串进 top=0; //行扫描并进行相应处理，得到结果(函数声 listArray=new float[size]; //明) } void compute(char* str); bool Stack::push(float it) int main() { { if(top==size) char str[20]; return false; cin.getline(str,20,'#'); listArray[top++]=it; compute(str); return true; return 0; } } bool Stack::pop(float& it) //此函数传进输入的字符串，并对字符串进{ //行扫描并进行相应处理，得到结果(函数体) if(top==0) void compute(char* str) return false; {

－ 3 －

数据结构课程实验指导书

Stack aStack; float x=0,y=0,s1,s2,temp; int i; i=0; while(str[i]) { switch(str[i]) {

case '+': //加法运算

if(aStack.isOne()||aStack.isEmpty()) {

cout << \表达式不符合要求\ return; } aStack.pop(s1); aStack.pop(s2); x=s2+s1; aStack.push(x); x=0;i++;break; case '-': //减法运算

if(aStack.isOne()||aStack.isEmpty()) { cout << \表达式不符合要求\ return; }

aStack.pop(s1); aStack.pop(s2); x=s2-s1;

aStack.push(x); x=0; i++; break;

case '*': //乘法运算

if(aStack.isOne()||aStack.isEmpty()) {

cout << \表达式不符合要求\ return; }

aStack.pop(s1); aStack.pop(s2); x=s2*s1;

aStack.push(x); x=0; i++; break;

case '/': //除法运算

if(aStack.isOne()||aStack.isEmpty())

{

cout << \表达式不符合要求\ return; }

aStack.pop(s1); aStack.pop(s2); if(s1==0) {

cout << \分母为0！\return; }

x=s2/s1;

aStack.push(x); x=0; i++; break;

case ' ': //如果是空格，将数据x押入栈中

if(str[i-1]>=48&&str[i-1]<=57) aStack.push(x); x=0; i++; y=0; break;

case '.': //获得小数部分

temp=10.0;

while(str[++i]!=' ') { if(str[i]>=48&&str[i]<=57) y=y+(str[i]-48)/temp; temp*=10; } x+=y; break;

default: //将字符数字转换为浮点型的数字

if(str[i]>=48&&str[i]<=57) {

x=x*10+str[i]-48;

i++; } } }

//判断栈是否只有切仅有一个元素，是就输//出结果

if(aStack.isOne()) {

4 －

－数据结构课程实验指导书

}

}

aStack.pop(x);

cout << str << '=' << x << endl;

－ 5 －

本文来源：https://www.bwwdw.com/article/rctf.html