长沙理工大学数据结构栈的实现及应用算术表达式求值实验报告

批 阅 实 验 报 告

年级 班号 学号

实验名称： 栈的实现及其应用：算术表达式的计算

实验日期 2016年12月 2日

实验报告撰写容 一、实验环境 二、实验目的 三、实验容

四、数据结构与算法思想描述 五、程序清单 六、程序执行结果及其分析 计算机科学与技术系

2016年制

Word文档

`

一、 实验环境

32位操作系统下的Window平台 Microsoft Visual C++

二、 实验目的

掌握栈的实现及使用

三、 实验容

1.实现栈的存储结构

2.实现栈的基本操作的有关算法 3.利用栈解决*算术表达式求值问题

四、 数据结构与算法思想描述

顺序读取中缀表达式：

1、 当遇到数字时，将数字入数字栈

2、 当遇到操作符时，与操作符栈栈顶比较：

If(当前操作符优先级大于操作符栈栈顶的优先级) If(非”)”操作符)

将当前操作符进操作符栈; Else

While(操作符栈栈顶不等于”(“)

取操作符栈栈顶及数字栈的两个数进行运算，并将结果压入数字栈; Else If(非(“操作符)

While(操作符栈栈顶不等于”(“)

取操作符栈栈顶及数字栈的两个数进行运算，并将结果压入数字栈; Continue;(直到当前操作符比栈顶操作符优先级大)

Else 将当前操作符进操作符栈; 3、 While(操作符栈非空)

操作符栈栈顶及数字栈的两个数进行运算，并将结果压入数字栈;

4、 在数字栈取最后结果并输出。

Word文档

`

五、 程序清单

//10*8^2+16.3+5*(5.2*5+3.01)/4-(-10)+0.1000060+4.00416-40 = 666.666666 //100+(-100)-(-10^2) = 100

//(((2016-2017+(((2015-2014)))))) = 0 //-1+(((((((((1^0))))))))+100%10^2 = 0 #include #include #include #include #include #include

typedef double Type; typedef struct {

Type TypeStack[MAX];

Word文档

`

char charStack[MAX]; int TypeTop, charTop;

}Stack;

//初始化栈

void InitStack(Stack *S) { }

//判断charStack是否为空 bool IsEmpty_Char(Stack S) { }

//判断TypeStack是否为空 bool IsEmpty_Type(Stack S) { }

//判断charStack是否为满 bool IsFull_Char(Stack S) {

return S.charTop == MAX; return S.TypeTop == 0; return S.charTop == 0; S->charTop = S->TypeTop = 0;

Word文档

`

}

//判断TypeStack是否为满 bool IsFull_Type(Stack S) { }

void Push_Char(Stack *S, char ch) { }

void Push_Type(Stack *S, Type a) { }

Word文档

return S.TypeTop == MAX;

//charStack不为满则入栈，否则输出提示 if(!IsFull_Char(*S))

S->charStack[S->charTop++] = ch;

else

cout << \" The CharStack Is Full! \" << endl;

//TypeStack不为满则入栈，否则输出提示 if(!IsFull_Type(*S))

S->TypeStack[S->TypeTop++] = a;

else

cout << \" The TypeStack Is Full! \" << endl;

`

char Pop_Char(Stack *S) { }

Type Pop_Type(Stack *S) { }

char Top_Char(Stack S) {

Word文档

if(!IsEmpty_Char(*S)) { } else

cout << \" The CharStack Is Empty! \" << endl; S->charTop--;

return S->charStack[S->charTop];

return -1;

if(!IsEmpty_Type(*S)) { } else

cout << \" The TypeStack Is Empty! \" << endl; S->TypeTop--;

return S->TypeStack[S->TypeTop];

return -1;

`

}

if(!IsEmpty_Char(S))

return S.charStack[--S.charTop];

else

cout << \" The CharStack Is Empty! \" << endl;

return -1;

Type Top_Type(Stack S) { }

Type Calculate(Type left, Type right, char op) {

Type value = 0; switch(op) {

case '+': value = left + right; break; case '-': value = left - right; break; case '*': value = left * right; break; case '/': if(right != 0)

value = left / right;

if(!IsEmpty_Type(S))

return S.TypeStack[--S.TypeTop];

else

cout << \" The TypeStack Is Empty! \" << endl;

return -1;

Word文档

`

}

else

cout << \"被除数不能为零!\" << endl;

break;

case '%': if(right != 0)

value = (int)left % (int)right;

else

cout << \"被余数不能为零!\" << endl;

break;

case '^': value = pow(left,right); /*value = 1; }

return value;

if(right >= 0)

while(right--)

value *= left;

else { }*/

right = -right; while(right--)

value /= left;

void Computer(char *mid_equotion, Type len) {

Word文档

`

Type right, left , result;

char *p_mid_equotion = mid_equotion; char after_equotion = ' ';

map Oper; Oper['#'] = 1;

Oper['('] = 2; Oper['+'] = 3;

Oper['/'] = 4;

Oper[')'] = 6;

Oper['-'] = 3; Oper['*'] = 4; Oper['%'] = 4;

Oper['^'] = 5;

Stack MyStack; InitStack(&MyStack); Push_Char(&MyStack,'#');

char top_oper, current_oper; for(;*p_mid_equotion != '\\0';) {

top_oper = Top_Char(MyStack); current_oper = *p_mid_equotion;

if(!Oper[current_oper]) {

Push_Type(&MyStack,strtod(p_mid_equotion, &p_mid_equotion)); continue;

}//end if else //为操作符 {

Word文档

`

if(Oper[current_oper] > Oper[top_oper]) { if(current_oper != ')')

Push_Char(&MyStack,current_oper);

else { while(top_oper != '(') { right = Pop_Type(&MyStack); if(!IsEmpty_Type(MyStack))

left = Pop_Type(&MyStack);

else

left = 0;

Push_Type(&MyStack,Calculate(left,

Top_Char(MyStack))); Pop_Char(&MyStack); top_oper = Top_Char(MyStack);

}

Pop_Char(&MyStack);

}//end else

}//end if else { if(current_oper == '(') {

Push_Char(&MyStack,current_oper);

Word文档

right,

`

}

if(*(p_mid_equotion + 1) == '-')

Push_Type(&MyStack,0);

else { }

right = Pop_Type(&MyStack); if(!IsEmpty_Type(MyStack))

left = Pop_Type(&MyStack);

else

left = 0;

Push_Type(&MyStack,Calculate(left, right, top_oper)); Pop_Char(&MyStack); continue;

}//end else

}//end else p_mid_equotion++;

}//end for

top_oper = Pop_Char(&MyStack); while(top_oper != '#') {

right = Pop_Type(&MyStack); if(!IsEmpty_Type(MyStack))

left = Pop_Type(&MyStack);

else

Word文档

`

}

left = 0;

Push_Type(&MyStack,Calculate(left, right, top_oper)); top_oper = Pop_Char(&MyStack);

// cout << setprecision(6) << \"\\nThe Result = \" << (result = Pop_Type(&MyStack)) << endl; } int main() { }

char s[MAX] = \"\"; Type i = 0;

cout << \"请输入你要求值的表达式!(以-1结束)\\n\"; while(cin >> s && strcmp(s,\"-1\") != 0) { } return 0;

Computer(s,strlen(s));

cout << \"请输入你要求值的表达式!(以-1结束)\\n\"; printf(\"The Result = %lf\\n\\n\

六、 程序执行结果及其分析

对 “+” , “-” , “*” , “/” , “%” , “^” 运算的实现

可运算多位数和小数，求余，求平方，括号里包含负数如（-1），及首个数字为负数如-1+1

Word文档

`

Word文档