使用堆栈来实现c语言的计算器.doc

栈的应用：C实现简单计算器（表达式的计算） 作为栈的著名应用，表达式的计算可以用下面方法实现： 首先建立两个栈，操作数栈NUM_S和运算符栈OPR_S。 其中，操作数栈用来存储表达式中的操作数；运算符栈用来存储表达式中的运算符。可以用字符‘=’来表示表达式结束符。 自左至右的扫描待处理的表达式，并假设当前扫描到的符号为W，根据不同的符号W做如下不同的处理： 1.若W为操作数，则将W压入操作数栈NUM_S，且继续扫描下一个字符； 2.若W为运算符，则根据运算符的性质做相应的处理： （0）若符号栈为空，无条件入栈当前指针指向的字符 （1）若w为不大于运算符栈栈顶的运算符，则从操作数栈NUM_S中弹出两个操作数，设先后弹出的操作数为a、b，再从运算符栈 OPR_S中弹出一个运算符，比如为+，然后作运算a+b,并将运算结果压入操作数栈NUM_S。 （2）若w为左括号或者运算符的优先级大于运算符栈栈顶的运算符，则将运算符W压入运算符栈OPR_S，并继续扫描下一个字符。 （3）若运算符W为右括号，循环操作（设先后弹出的操作数为a、b，再从运算符栈OPR_S中弹出一个运算符，比如为+，然后作运 算a+b, 并将运算结果压入操作数栈NUM_S），直到从运算符栈中弹出第一个左括号。 （4）若运算符W为表达式结束符‘=’，循环操作（设先后弹出的操作数为a、b，再从运算符栈OPR_S中弹出一个运算符，比如为 +，然后作运算a+b, 并将运算结果压入操作数栈NUM_S），直到运算符栈为空为止。此时，操作数栈栈顶元素即为表达式的 值。 ========================================================================= 举例： 计算 3+(5-2*3)/4-2= （1） 开始栈为空，3入栈，+入栈，（无条件入栈，5入栈，-号优先级比（高，所以-号入栈，2入栈，*优先级比目前栈顶的-号优先级高，所以*入栈，3入栈，接着扫描到）括号，）括号不入栈 | | | | --------- ---------- | 3 | | * | --------- ---------- | 2 | | - | --------- ---------- | 5 | | ( | --------- ---------- | 3 | | + | --------- ---------- 操作数栈 操作符栈 （2） 在）括号碰到（括号之前，让操作数栈一直出栈，直到让左括号出栈为止 所以： 2，3弹出操作数栈，*弹出操作符号栈，计算 2*3 = 6，然后将6入操作数栈 | | | | --------- ---------- | | | | --------- ---------- | 6 | | - | --------- ---------- | 5 | | ( | --------- ---------- | 3 | | + | --------- ---------- 操作数栈 操作符栈 （3） 接着6，5弹出操作数栈，-弹出操作符栈，计算 5-6 = -1， 然后将-1入操作数栈，然后左括号出栈 | | | | --------- ---------- | | | | --------- ---------- | | | | --------- ---------- | -1 | | | --------- ---------- | 3 |