一种改进的逆波兰计算器
本帖最后由 代号-K 于 2020-3-17 16:56 编辑听了小甲鱼的逆波兰算法，发现其中有很大的bug；
当要计算的算式 出现乘法与除法同时存在时，会出现转换错误，例如
1 + 2 - 3 * 4 / 5 * 6 会转换成 1 2 + 3 4 5 6 * / * - ，明显出现转换错误
解决方法：定义优先级 除法的优先级比乘法高一点
#ifndef POLANDOPERATOR_H
#define POLANDOPERATOR_H
#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#include "stack.h"
#include <QHash>
#define MAX_BUFF_VOLUMN 16
template<class T>
class PolandOperator
{
public:
PolandOperator(Stack<T> *S)
{
this->stack = S;
charHash.insert('+',0);
charHash.insert('-',0);
charHash.insert('*',1);
charHash.insert('/',2);
charHash.insert('^',3);
}
T getResult(char *buff)
{
char str = {0};
char *p = buff;
int i = 0;
T d, e;
while(*p != '\0')
{
// filter digit
while(isdigit(*p) || *p == '.')
{
str = *p;
// use to end
str = '\0';
if(i >=MAX_BUFF_VOLUMN)
{
printf("error, this number is too big\n");
return -1;
}
p++;
//space
if(*p == 32)
{
d = atof(str);
stack->push(d);
i = 0;
break;
}
}
switch (*p) {
case '+':
stack->pop(&e);
stack->pop(&d);
stack->push(d+e);
break;
case '-':
stack->pop(&e);
stack->pop(&d);
stack->push(d-e);
break;
case '*':
stack->pop(&e);
stack->pop(&d);
stack->push(d*e);
break;
case '/':
stack->pop(&e);
stack->pop(&d);
if(e != 0)
{
stack->push(d/e);
}
else
{
printf("\n error, zero\n");
return -1;
}
break;
case '^':
stack->pop(&e);
stack->pop(&d);
stack->push((T)pow(d,e));
break;
}
p++;
}
stack->pop(&d);
return d;
}
void getPolandExpression(char *buff, char *ret)
{
char*p = buff;
char e;
while(*p != '\0')
{
//digit
while((*p >= '0' && *p <= '9') || *p == '.')
{
*ret++ = *p++;
}
*ret++ = 32;
// operator
charIter = charHash.find(*p);
if(charIter == charHash.end()){
if('(' == *p) stack->push(*p);
else if(')' == *p)
{
stack->pop(&e);
while('(' != e)
{
*ret++ = e;
*ret++ = 32;
stack->pop(&e);
}
}
}else if(charIter != charHash.end()){
//four operators
if(!stack->stackLen()) stack->push(*p);
else{
do{
stack->pop(&e);
if('(' == e) stack->push(e);
else{
if(charIter.value() <= charHash.find(e).value()){
*ret++ = e;
*ret++ = 32;
}else{
stack->push(e);
break;
}
}
}while(stack->stackLen() && '(' != e);
stack->push(*p);
}
}
p++;
}
while (stack->stackLen()) {
stack->pop(&e);
*ret++ = e;
*ret++ = 32;
}
*ret = '\0';
}
private:
Stack<T> *stack;
QHash<char, int> charHash;
QHash<char, int>::iterator charIter;
};
#endif // POLANDOPERATOR_H
栈的实现
#ifndef STACK_H
#define STACK_H
#include <stdlib.h>
#include <stdio.h>
#include <stack>
#define MAXSIZE 20
#define STACKINCREMENT 10
// define element type
//typedef double ElemType;
template<class T>
struct Node
{
T *base;
T *top;
int stackSize;
};
template<class T>
class Stack
{
public:
Stack(struct Node<T> *S)
{
this->S = S;
initStack();
}
Stack(){}
void initStack()
{
S->base = (T *)malloc(MAXSIZE *sizeof(T));
if(!S->base)
{
printf("alloc failure\n");
exit(-1);
}
S->top = S->base;
S->stackSize = MAXSIZE;
}
void initStack(struct Node<T>*S)
{
this->S = S;
initStack();
}
void push(T e)
{
// stack is full
if((S->top) - (S->base) >= (S->stackSize))
{
S->base = (T*)realloc(S->base, (S->stackSize + STACKINCREMENT)*sizeof(T));
if(!S->base)
{
printf("realloc failure\n");
exit(-1);
}
S->top = (S->base) +(S->stackSize);
S->stackSize = S->stackSize + STACKINCREMENT;
}
*(S->top) = e;
S->top++;
}
void pop(T *e)
{
if(S->top == S->base)
{
printf("stack is empty\n");
return;
}
// top always point is empty, so must S->top--;
*e = *--(S->top);
}
int stackLen(void)
{
return (S->top-S->base);
}
private:
struct Node<T> *S;
};
#endif // STACK_H
#include "stack.h"
#include "polandoperator.h"
typedef double Element;
typedef char ConvertEle;
int main(int argc, char *argv[])
{
QCoreApplication a(argc, argv);
//convert polandExpression
char retArray = {0};
char buff = "2.4*3.6/2^2";
struct Node<ConvertEle> s1;
Stack<ConvertEle> stack1(&s1);
PolandOperator<ConvertEle> pld1(&stack1);
pld1.getPolandExpression(buff, retArray);
char *p = retArray;
while(*p != '\0')
{
printf("%c",*p);
p++;
}
printf("\n");
//computer polandExpression
struct Node<Element> s;
Stack<Element> stack(&s);
PolandOperator<Element> pld(&stack);
double ret = pld.getResult(retArray);
printf("%f\n", ret);
return 0;
}
实例的实现
页:
[1]