设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 技术交流 › 数据结构与算法 › 一种改进的逆波兰计算器
返回列表 发新帖
查看: 1519|回复: 0

[技术交流] 一种改进的逆波兰计算器

[复制链接]
代号-K
发表于 2020-3-17 15:53:12 | 显示全部楼层 |阅读模式

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

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

x
本帖最后由 代号-K 于 2020-3-17 16:56 编辑

听了小甲鱼的逆波兰算法，发现其中有很大的bug；
当要计算的算式 出现乘法与除法同时存在时，会出现转换错误，例如
1 + 2 - 3 * 4 / 5 * 6 会转换成 1 2 + 3 4 5 6 * / * - ，明显出现转换错误
解决方法：定义优先级 除法的优先级比乘法高一点

  1. #ifndef POLANDOPERATOR_H
  2. #define POLANDOPERATOR_H
  3. #include <stdlib.h>
  4. #include <stdio.h>
  5. #include <ctype.h>
  6. #include "stack.h"
  7. #include <QHash>

  9. #define MAX_BUFF_VOLUMN 16

  11. template<class T>
  12. class PolandOperator
  13. {
  14. public:
  15.     PolandOperator(Stack<T> *S)
  16.     {
  17.         this->stack = S;
  18.         charHash.insert('+',0);
  19.         charHash.insert('-',0);
  20.         charHash.insert('*',1);
  21.         charHash.insert('/',2);
  22.         charHash.insert('^',3);
  23.     }

  25.     T getResult(char *buff)
  26.     {
  27.         char str[MAX_BUFF_VOLUMN] = {0};
  28.         char *p = buff;
  29.         int i = 0;
  30.         T d, e;
  31.         while(*p != '\0')
  32.         {
  33.             // filter digit
  34.             while(isdigit(*p) || *p == '.')
  35.             {
  36.                 str[i++] = *p;
  37.                 // use to end
  38.                 str[i] = '\0';
  39.                 if(i >=  MAX_BUFF_VOLUMN)
  40.                 {
  41.                     printf("error, this number is too big\n");
  42.                     return -1;
  43.                 }
  44.                 p++;
  45.                 //space
  46.                 if(*p == 32)
  47.                 {
  48.                     d = atof(str);
  49.                     stack->push(d);
  50.                     i = 0;
  51.                     break;
  52.                 }
  53.             }
  54.             switch (*p) {
  55.             case '+':
  56.                 stack->pop(&e);
  57.                 stack->pop(&d);
  58.                 stack->push(d+e);
  59.                 break;
  60.             case '-':
  61.                 stack->pop(&e);
  62.                 stack->pop(&d);
  63.                 stack->push(d-e);
  64.                 break;
  65.             case '*':
  66.                 stack->pop(&e);
  67.                 stack->pop(&d);
  68.                 stack->push(d*e);
  69.                 break;
  70.             case '/':
  71.                 stack->pop(&e);
  72.                 stack->pop(&d);
  73.                 if(e != 0)
  74.                 {
  75.                     stack->push(d/e);
  76.                 }
  77.                 else
  78.                 {
  79.                     printf("\n error, zero\n");
  80.                     return -1;
  81.                 }
  82.                 break;
  83.             case '^':
  84.                 stack->pop(&e);
  85.                 stack->pop(&d);
  86.                 stack->push((T)pow(d,e));
  87.                 break;
  88.             }
  89.             p++;
  90.         }
  91.         stack->pop(&d);
  92.         return d;
  93.     }

  95.     void getPolandExpression(char *buff, char *ret)
  96.     {
  97.         char*p = buff;
  98.         char e;
  99.         while(*p != '\0')
  100.         {
  101.             //digit
  102.             while((*p >= '0' && *p <= '9') || *p == '.')
  103.             {
  104.                 *ret++ = *p++;
  105.             }
  106.             *ret++ = 32;

  108.             // operator
  109.             charIter = charHash.find(*p);
  110.             if(charIter == charHash.end()){
  111.                 if('(' == *p) stack->push(*p);
  112.                 else if(')' == *p)
  113.                 {
  114.                     stack->pop(&e);
  115.                     while('(' != e)
  116.                     {
  117.                         *ret++ = e;
  118.                         *ret++ = 32;
  119.                         stack->pop(&e);
  120.                     }
  121.                 }
  122.             }else if(charIter != charHash.end()){
  123.                 //four operators
  124.                 if(!stack->stackLen()) stack->push(*p);
  125.                 else{
  126.                     do{
  127.                         stack->pop(&e);
  128.                         if('(' == e) stack->push(e);
  129.                         else{
  130.                             if(charIter.value() <= charHash.find(e).value()){
  131.                                 *ret++ = e;
  132.                                 *ret++ = 32;
  133.                             }else{
  134.                                 stack->push(e);
  135.                                 break;
  136.                             }
  137.                         }
  138.                     }while(stack->stackLen() && '(' != e);
  139.                     stack->push(*p);
  140.                 }
  141.             }
  142.             p++;
  143.         }
  144.         while (stack->stackLen()) {
  145.             stack->pop(&e);
  146.             *ret++ = e;
  147.             *ret++ = 32;
  148.         }
  149.         *ret = '\0';
  150.     }

  152. private:
  153.     Stack<T> *stack;
  154.     QHash<char, int> charHash;
  155.     QHash<char, int>::iterator charIter;
  156. };

  158. #endif // POLANDOPERATOR_H
复制代码


栈的实现
  1. #ifndef STACK_H
  2. #define STACK_H

  4. #include <stdlib.h>
  5. #include <stdio.h>
  6. #include <stack>
  7. #define MAXSIZE 20
  8. #define STACKINCREMENT 10

  10. // define element type

  12. //typedef double ElemType;
  13. template<class T>
  14. struct Node
  15. {
  16.     T *base;
  17.     T *top;
  18.     int stackSize;
  19. };


  22. template<class T>
  23. class Stack
  24. {

  26. public:
  27.     Stack(struct Node<T> *S)
  28.     {
  29.         this->S = S;
  30.         initStack();
  31.     }
  32.     Stack(){}

  34.     void initStack()
  35.     {
  36.         S->base = (T *)malloc(MAXSIZE *sizeof(T));
  37.         if(!S->base)
  38.         {
  39.             printf("alloc failure\n");
  40.             exit(-1);
  41.         }
  42.         S->top = S->base;
  43.         S->stackSize = MAXSIZE;
  44.     }
  45.     void initStack(struct Node<T>*S)
  46.     {
  47.         this->S = S;
  48.         initStack();
  49.     }

  51.     void push(T e)
  52.     {
  53.         // stack is full
  54.         if((S->top) - (S->base) >= (S->stackSize))
  55.         {
  56.             S->base = (T*)realloc(S->base, (S->stackSize + STACKINCREMENT)*sizeof(T));
  57.             if(!S->base)
  58.             {
  59.                 printf("realloc failure\n");
  60.                 exit(-1);
  61.             }
  62.             S->top = (S->base) +(S->stackSize);
  63.             S->stackSize = S->stackSize + STACKINCREMENT;
  64.         }
  65.         *(S->top) = e;
  66.         S->top++;
  67.     }
  68.     void pop(T *e)
  69.     {
  70.         if(S->top == S->base)
  71.         {
  72.             printf("stack is empty\n");
  73.             return;
  74.         }
  75.         // top always point is empty, so must S->top--;
  76.         *e = *--(S->top);
  77.     }
  78.     int stackLen(void)
  79.     {
  80.         return (S->top-S->base);
  81.     }

  83. private:
  84.     struct Node<T> *S;
  85. };

  87. #endif // STACK_H
复制代码

  2. #include "stack.h"
  3. #include "polandoperator.h"

  5. typedef double Element;
  6. typedef char ConvertEle;
  7. int main(int argc, char *argv[])
  8. {
  9.     QCoreApplication a(argc, argv);

  11.     //convert polandExpression
  12.     char retArray[64] = {0};
  13.     char buff[32] = "2.4*3.6/2^2";
  14.     struct Node<ConvertEle> s1;
  15.     Stack<ConvertEle> stack1(&s1);
  16.     PolandOperator<ConvertEle> pld1(&stack1);
  17.     pld1.getPolandExpression(buff, retArray);
  18.     char *p = retArray;
  19.     while(*p != '\0')
  20.     {
  21.         printf("%c",*p);
  22.         p++;
  23.     }
  24.     printf("\n");

  26.     //computer polandExpression
  27.     struct Node<Element> s;
  28.     Stack<Element> stack(&s);
  29.     PolandOperator<Element> pld(&stack);
  30.     double ret = pld.getResult(retArray);
  31.     printf("%f\n", ret);
  32.     return 0;
  33. }
复制代码

实例的实现
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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

GMT+8, 2024-5-23 15:47

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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