鱼C论坛

 找回密码
 立即注册
查看: 2501|回复: 0

[学习笔记] 表达式求值

[复制链接]
发表于 2018-4-19 08:50:58 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
《数据结构C++描述》清华大学出版社  任燕编著

小弟简单改写了书上的程序,使之可以运行,同时在顺序栈那里也是改了书上的一个bug
程序小弟调试了应该没有错,要是有错欢迎来指出,
数据结构真有意思,嘿嘿

从大约190行开始时逆波兰表达式的转化和求值的一些函数
之前的顺序栈的定义和一些方法可以滤去不看(若是您很清楚的话)
在输入表达式值的时候建议要用英文状态下的字符,同时不要有空格
  1. #include <iostream>
  2. #include <assert.h>
  3. #include <cstdlib>
  4. #include <cstdbool>
  5. #define STACK_MAX_SIZE 100
  6. #define STACKINCREAMENT 10
  7. using namespace std;
  8. ///////////////////////////////////////////////////////////
  9. //栈的结构定义和一些方法的应用
  10. template <typename elemtype>
  11. class SqStack{
  12. public:
  13.         //顺序栈置空
  14.         void clear();

  15.         //求顺序栈中元素的个数
  16.         int getLength();

  17.         //返回档期那已经分派的存储空间的大小
  18.         int getStackSize();

  19.         //读取栈顶元素
  20.         bool getTop(elemtype &e);

  21.         //判断顺序栈是否为空
  22.         bool isEmpty();

  23.         //重载赋值运算符
  24.         SqStack operator=(SqStack right);

  25.         //弹出栈顶元素
  26.         bool pop(elemtype &e);

  27.         //在栈顶压入元素e
  28.         void push(elemtype e);

  29.         //构造函数
  30.         SqStack();

  31.         //析构函数
  32.         virtual ~SqStack();

  33.         //拷贝构造函数
  34.         SqStack(SqStack &other);

  35.         //重载输出运算符
  36.         template <typename out_put>
  37.         friend ostream& operator <<(ostream& out, SqStack<out_put> other);

  38. protected:
  39.         elemtype *base;//栈底指针,就是顺序栈动态存储空间的首地址
  40.         elemtype *top;//栈顶指针
  41.         int stackSize;//顺序栈当前已经分配的存储空间的大小
  42. };


  43. template <typename elemtype>
  44. void SqStack<elemtype>::clear(){
  45.         top = base;
  46.         cout << "顺序栈已经清空" << endl;
  47. }

  48. template <typename elemtype>
  49. int SqStack<elemtype>::getLength(){
  50.         return top - base;
  51. }

  52. template <typename elemtype>
  53. int SqStack<elemtype>::getStackSize(){
  54.         return stackSize;
  55. }

  56. //读取栈顶的元素
  57. template <typename elemtype>
  58. bool SqStack<elemtype>::getTop(elemtype &e){
  59.         if (isEmpty()){
  60.                 return false;
  61.         }
  62.         else{
  63.                 e = *(top - 1);
  64.         }
  65.         return true;
  66. }

  67. template <typename elemtype>
  68. bool SqStack<elemtype>::isEmpty(){
  69.         return top == base ? true : false;
  70. }

  71. //重载赋值运算符
  72. template <typename elemtype>
  73. SqStack<elemtype> SqStack<elemtype>::operator =(SqStack<elemtype> right){
  74.         int length = right.getLength();

  75.         if (this != &right){
  76.                 if (stackSize < right.stackSize){
  77.                         delete[] base;  //回收左边的顺序栈的存取空间
  78.                         base = new elemtype[right.stackSize];
  79.                         assert(base != 0);
  80.                         stackSize = right.stackSize;//进行属性的一些重新的赋值
  81.                 }

  82.                 for (int i = 0; i < length; i++){
  83.                         *(base + i) = *(right.base + i);
  84.                 }
  85.                 top = base + length();
  86.         }
  87.         return *this;//返回对象
  88. }

  89. //弹出栈顶元素到e
  90. template <typename elemtype>
  91. bool SqStack<elemtype>::pop(elemtype &e){
  92.         if (isEmpty()){
  93.                 return false;
  94.         }
  95.         else{
  96.                 e = *--top;
  97.         }
  98.         return true;
  99. }

  100. //在栈顶压入元素e
  101. template <typename elemtype>
  102. void SqStack<elemtype>::push(elemtype e){
  103.         int length = top - base;//顺序栈中元素的个数
  104.         elemtype *newBase;//预指向新顺序栈的栈底指针
  105.         //判断当前顺序栈是否已满,如果满了,则需要另外申请存储空间
  106.         if (top - base >= stackSize){
  107.                 newBase = new elemtype[stackSize + STACKINCREAMENT];
  108.                 assert(newBase != 0);

  109.                 for (int j = 0; j < length; j++){
  110.                         *(newBase + j) = *(base + j);
  111.                 }

  112.                 delete[] base;//回收当前已经满了的栈空间
  113.                 base = newBase;
  114.                 top = base + length;
  115.         }

  116.         //如果当前顺序栈没有满,就不用重新申请空间了,就直接以下两个语句就行了
  117.         *top = e;
  118.         top++;
  119. }


  120. template <typename elemtype>
  121. SqStack<elemtype>::SqStack(){
  122.         base = new elemtype[STACK_MAX_SIZE];//申请空间
  123.         assert(base != 0);
  124.         stackSize = STACK_MAX_SIZE;//属性的赋值
  125.         top = base;//栈的初始为空
  126. }

  127. //你懂的
  128. template <typename elemtype>
  129. SqStack<elemtype>::~SqStack(){
  130.         if (base){
  131.                 delete[]base;
  132.         }
  133.         stackSize = 0;
  134.         top = base = NULL;
  135. }

  136. template <typename elemtype>
  137. SqStack<elemtype>::SqStack(SqStack &other){
  138.         int length = other.top - other.base;
  139.         base = new elemtype[other.stackSize];

  140.         assert(base != 0);

  141.         stackSize = other.stackSize;
  142.         for (int i = 0; i < length; i++){
  143.                 *(base + i) = *(other.base + i);
  144.         }
  145.         top = base + length;
  146. }

  147. template <typename out_put>
  148. ostream& operator<<(ostream& out, SqStack<out_put> other){
  149.         int length = other.top - other.base;
  150.         for (int i = 0; i < length; i++){
  151.                 out << *(other.base + i) << "\t";
  152.         }

  153.         return out;
  154. }



  155. /////////////////////////////////////////////////////////////////
  156. //下面开始写中缀表达式向后缀表达式的函数

  157. //判断是运算符,数字字符或者是其他的字符
  158. int isOpMember(char ch){
  159.         if (ch == '0' || ch == '1' ||
  160.                 ch == '2' || ch == '3' ||
  161.                 ch == '4' || ch == '5' ||
  162.                 ch == '6' || ch == '7' ||
  163.                 ch == '8' || ch == '9'){
  164.                 return 0;
  165.         }
  166.         else if (ch == '+' || ch == '-' ||
  167.                 ch == '*' || ch == '/' ||
  168.                 ch == '(' || ch == ')' ||
  169.                 ch == '\0'){
  170.                 return 1;
  171.         }
  172.         else{
  173.                 return -1;
  174.         }
  175. }


  176. //各种运算符在运算符优先级矩阵的对应的下标
  177. int order(char m){
  178.         switch (m){
  179.         case '+':return 0;
  180.         case '-':return 1;
  181.         case '*':return 2;
  182.         case '/':return 3;
  183.         case '(':return 4;
  184.         case ')':return 5;
  185.         case '\0':return 6;
  186.         default:return 7;
  187.         }
  188. }


  189. //判定两个运算符的优先级的高低
  190. int precede(char op1, char op2){
  191.         //运算符优先级矩阵
  192.         int inCmpOut[7][7] = { { 1, 1, -1, -1, -1, 1, 1 },
  193.         { 1, 1, -1, -1, -1, 1, 1 },
  194.         { 1, 1, 1, 1, -1, 1, 1 },
  195.         { 1, 1, 1, 1, -1, 1, 1 },
  196.         { -1, -1, -1, -1, -1, 0, 0 },
  197.         { 1, 1, 1, 1, 2, 1, 1 },
  198.         { -1, -1, -1, -1, -1, 2, 0 } };
  199.         int i, j;
  200.         i = order(op1);//op1在矩阵中的下标,作为行号
  201.         j = order(op2);//op2在矩阵中的下标,作为列号
  202.         return inCmpOut[i][j];
  203. }

  204. //中缀表达式转化为后缀表达式
  205. //输入:函数的参数midS为待转换的中缀表达式
  206. //输出:函数的参数suffixS为midS对应的后缀表达式
  207. void transform(char *midS, char *suffixS){
  208.         int i = 0;//后缀表达式当前处理字符的下标,初始化为0
  209.         int j = 0;//中缀表达式当前处理字符的下标,初始化为0
  210.         char ch = midS[0];//中缀表达式当前处理字符,初始化为第一个字符
  211.         //中缀表达式转化为后缀的过程中,遇到运算符是不能直接进入到后缀表达式中的
  212.         //他们要让后面较高级别的运算符先进入,所以用运算符栈S先暂存这些
  213.         //还不能进入到后缀表达式的运算符
  214.         SqStack<char> S;
  215.         char op;//预存放运算符栈S弹出的栈顶元素

  216.         //把运算符'\0'压栈,它是最低级别的运算符,如果最后弹出此运算符,则表明已经完成转化
  217.         S.push('\0');

  218.         //从中缀表达式的第一个字符开始,知道结束,逐一扫描,分别转化
  219.         while (!S.isEmpty()){
  220.                 if (!isOpMember(ch)){//如果是操作数
  221.                         if (i > 0 && isOpMember(suffixS[i - 1]) == 1){
  222.                                 suffixS[i++] = ' ';//如果是新操作数,就添加空格
  223.                         }
  224.                         suffixS[i++] = ch;//直接进入后缀表达式
  225.                 }
  226.                 else{//如果是运算符
  227.                         if (i > 0 && suffixS[i - 1] != ' '){
  228.                                 suffixS[i++] = ' ';
  229.                         }
  230.                         switch (ch){
  231.                         case '('://左括号直接入栈
  232.                                 S.push(ch);
  233.                                 break;
  234.                         case ')':
  235.                                 S.pop(op);
  236.                                 while (op != '('){
  237.                                         suffixS[i++] = op;
  238.                                         suffixS[i++] = ' ';
  239.                                         S.pop(op);
  240.                                 }
  241.                                 --i;//回到原来i的位置
  242.                                 break;
  243.                         default://其他情况的运算符例如+-*/等
  244.                                 while (S.getTop(op)){
  245.                                         if (precede(op, ch) == 1 || precede(op, ch) == 0){
  246.                                                 suffixS[i++] = op;
  247.                                                 suffixS[i++] = ' ';
  248.                                         }
  249.                                         else{
  250.                                                 break;
  251.                                         }
  252.                                         S.pop(op);//写入后缀表达式后要弹栈
  253.                                 }
  254.                                 //如果中缀表达式当前字符不是'\0',则压入运算符栈
  255.                                 if (ch != '\0'){
  256.                                         S.push(ch);
  257.                                 }
  258.                         }
  259.                 }
  260.                 if (ch != '\0'){
  261.                         ch = midS[++j];
  262.                 }
  263.         }
  264.         suffixS[i] = '\0';//放入最后一个单元,完成转化
  265. }

  266. //指定运算符的运算
  267. double caculate(double a, char ch, double b){
  268.         switch (ch){
  269.         case '+':return a + b;
  270.         case '-':return a - b;
  271.         case '*':return a*b;
  272.         case '/':return a / b;
  273.         default:return -1;
  274.         }
  275. }


  276. //后缀表达式的计算
  277. double evaluation(char *suffixS){
  278.         int i = 0;//后缀表达式的当前字符的下标,初始化为0
  279.         char ch = suffixS[i];//后缀表达式当前字符,初始化为第一个字符
  280.         double x;//预存放当前操作数

  281.         SqStack<double> S;//后缀表达式中计算的时候要用到顺序栈来进行运算
  282.         double a, b;

  283.         //从后缀表达式的第一个字符开始,直到结束,分别处理
  284.         while (ch != '\0'){
  285.                 if (isOpMember(ch) == 0){
  286.                         x = 0;
  287.                         while (isOpMember(ch) == 0){//如果当前是操作数
  288.                                 x = 10 * x + (ch - '0');
  289.                                 ch = suffixS[++i];
  290.                         }
  291.                         S.push(x);
  292.                 }
  293.                 else if (isOpMember(ch) == 1){//如果当前是运算符
  294.                         S.pop(b);
  295.                         S.pop(a);
  296.                         S.push(caculate(a, ch, b));
  297.                 }
  298.                 ch = suffixS[++i];
  299.         }
  300.         S.pop(x);//从栈中弹出结果
  301.         return x;//返回结果
  302. }


  303. int main(void){
  304.         char midS[128];
  305.         char suffixS[128];
  306.         cout << "请输入一个表达式:" << endl;
  307.         cin >> midS;
  308.         transform(midS, suffixS);//调用中缀表达式转化为后缀表达式的函数
  309.         cout << "后缀表达式为:" << endl;
  310.         cout << suffixS << endl;
  311.         cout << "计算结果为:" << endl;
  312.         cout << evaluation(suffixS) << endl;
  313.         return 0;
  314. }



复制代码



运行结果:
请输入一个表达式:
23-((34-13)*7+6/2)
后缀表达式为:
23 34 13 - 7 * 6 2 / + -
计算结果为:
-127
请按任意键继续. . .
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 14:20

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表