课程设计的内容和要求(包括原始数据、技术要求、工作要求等)
编写程序实现栈与表达式式求值即验证某算术栈与表达式式的正确性,若正确则计算该算术栈与表達式式的值。
1、从键盘上输入栈与表达式式
2、分析该栈与表达式式是否合法:
(1)是数字,则判断该数字的合法性若合法,则压入数據到堆栈中
(2)是规定的运算符,则根据规则进行处理在处理过程中,将计算该栈与表达式式的值
(3)若是其它字符,则返回错误信息
对于连个相继出现的操作符θ1和θ2 有三种关系:大于、等于和小于。由此可以列出“+-*/”之间的优先级如下表:
加减乘除优先性都低于“(”但是高于“)”,由运算从左到右可知当θ1=θ2 ,令θ1>θ2
为了算法简洁在栈与表达式式的左边和右边虚设一个“#”,这一对“#”表示一个栈与表达式式求值完成
“(”=“)”当一对括号相遇时表示括号内已运算完成。
“)”和“(”、“#”和“(”、“(”和“#”无法相继出现如果出现则栈与表达式式出现语法错误
为实现优先算法,可以使用两个工作栈一个是OPTR,用于寄存运算符一个是OPND,用於寄存运算数和运算结果
首先置操作数栈为空栈,栈与表达式式起始符为“#”为栈底元素
依次读入栈与表达式式中的每个字符,若是操作数则进OPND栈若是运算符则和OPTR栈的栈顶运算符比较优先权作相应操作,直至整个栈与表达式式求值完毕(OPTR栈顶元素和当前读入的字符均為“#”) char pre; //记录当前字符的前一个字符用于负数的判断