栈的应用—中缀转后缀求表达式值
栈的应用有很多，我们最熟悉的函数调用与递归等对编译器来说都是用栈的工作原理来实现的。还有我们的浏览器中有一个向后退选项，这就是一个栈的应用了（这个是<大话数据结构>中的举例）。还有就是本篇要讲的表达式求值了。我们知道C/C++是基于表达式的程序设计语言，可见表达式对于语言的重要性了。至于什么是表达式等话题这里就不讨论了，直接说表达式的三种类型，他们分别是：前缀表达式，中缀表达式，后缀表达式。在这里只讲对于双目运算符的情况，单目与三目等不作讨论。
中缀表示形式：<操作数><操作符><操作数>，例如A+B
前缀表示形式：<操作符><操作数><操作数>，例如+AB
后缀表示形式：<操作数><操作数><操作数>，例如AB+
利用中缀形式求表达式的值，在各种程序设计语言和计算器中也经常使用，需要使用两个栈，一个存放操作数，一个存放操作符。在这里我们只讲述如何利用后缀形式求表达式的值。
利用后缀形式求表达式的值只需要一个栈即可，且操作方便，但由中缀形式的表达式转换为后缀形式就需要一个算法与过程了。
先给出一个中缀形式的表达式：A + B * (C - D) - E / F，其后缀形式为：ABCD- * + EF / -。如何将其转换为一个后缀形式的表达式呢？这需要一个算法实现，在展开算法之前要考虑几个问题，一个是怎么将操作符的优先级表现在其后缀形式的顺序中，一个是括号怎么处理。
针对第一个问题，我们将各个常见的二目运算符进行一个优先级的排序
操作符 ch # ( *,/,% +,- )
isp 0 1 6 3 6
icp 0 6 4 2 1
因为要先压栈一个符号作为标志，所以定义#为0，意思是所有的操作符都比他的优先级高。isp与icp是操作符在栈内栈外的优先级是不同的，isp(in stack prioroty) ，icp(in coming priority)。
现在问题都解决了，就是一个算法的实现了，下面请看算法：
<1> 操作符栈初始化，将结束符'#'压入栈。然后读入中缀表达式的首字符ch。
<2> 重复执行以下步骤，直到ch = '#'同时栈顶的操作符也是'#'时，停止循环。
a:若ch是操作符直接输出，读入下一个字符ch。
b:若是操作符，判断ch的优先级icp值域位于栈顶的操作符op的优先级isp值:
@若icp(ch) > isp(op)，另ch进栈，读入下一个字符。
@若icp(ch) < isp(op)，退出栈顶操作符并输出该字符，注意这里没有读入下一个字符而是继续循环比较栈中的元素。这一步专门为了括号考虑的。
@若icp(ch) == isp(op)，退栈但不输出，若退出的是'('号，读入下一个字符ch。
<3> 算法结束，输出序列即为所需要的后缀表达式。
下面就贴代码了：
[cpp]
#pragma once
#include<iostream>
//#include<stack>//STL中的栈 自己的栈也可以达到这个效果
#include"S_stack.h"
#include<vector>
#include<string>
using namespace std;
class Calculator
{
private:
string expression_str;//用于用户输入的表达式承接的字符串
vector<char> char_elem;//中缀转换成后缀后的字符容器 动态增长
Stack<float> stk_float;//用于后缀计算表达式的浮点数栈 核心变量
void Do_Operator(char opt_ch);//根据操作符 去栈中去取两个元素计算
bool Get_operands(float &left_optnum,float &right_optnum);//从栈中取出左和右操作数 用于计算
bool is_numelem(char ch);//判断是否为操作数
float exchange_num(char num_ch);//数值型字符转换成数字
void exchange_exp();//中缀转换为后缀的表达式存放在字符数组中，便于后缀计算
int Get_isp(char opt_ch);//返回操作符的栈内优先级数
int Get_icp(char opt_ch);//返回即将进栈操作符的优先级数
void Show_result();//返回计算结果
public:
Calculator(string str);//计算器接受一个字符串型表达式
~Calculator();
void Running();//对外计算接口
};
[cpp]
#include"Calculator.h"
#include<iostream>
using namespace std;
//初始化 一些数据 用于后期计算
Calculator::Calculator(string str)
{
expression_str = str;
}
Calculator::~Calculator()
{
}
//返回操作符的栈内优先级数
int Calculator::Get_isp(char opt_ch)
{
switch(opt_ch)
{
case'#':
return 0; break;
case'(':
return 1; break;
case'*':case'/':case'%':
return 5; break;
case'+':case'-':
return 3; break;
case')':
return 6; break;
}
}
//返回即将进栈操作符的优先级数
int Calculator::Get_icp(char opt_ch)
{
switch(opt_ch)
{
case'#':
return 0; break;
case'(':
return 6; break;
case'*':case'/':case'%':
return 4; break;
case'+':case'-':
return 2; break;
case')':
return 1; break;
}
}
//判断是否为操作数
bool Calculator::is_numelem(char ch)
{
if(48<=ch && ch<=57)//这里的局限性是 只能判断和后期计算10以内的四则运算
return true;
else
return false;
}
//中缀转换为后缀的表达式存放在字符数组中，便于后缀计算
补充：软件开发 , C++ ,
- 更多C/C++疑问解答：
- 关于c++的cout输出的问题。
- 在学校里学过C和C++，不过学的很一般，现在自学C#，会不会很难？
- 全国计算机二级C语言笔试题
- 已知某树有2个2度结点，3个3度结点，4个4度结点，问有几个叶子结点？
- c++数据结构内部排序问题，整数排序
- 2012九月计算机二级C语言全国题库，，急求急求
- 如果assert只有一个字符串作为参数，是什么意思呢?
- C语言中，哪些运算符具有左结合性，哪些具有右结合性，帮忙总结下，谢谢了！
- 为什么用结构体编写的程序输入是，0输不出来啊~~~
- 将IEEE—754的十六进制转化为十进制浮点类型，用C或C++都行，多谢各位大侠啊，非常感谢！
- 为什么这个程序求不出公式？
- 这个链表倒置的算法请大家分析下
- c语言函数库调用
- C语言unsigned int纠错
- C语言快排求解啊