一种改进的逆波兰计算器

代号-K

听了小甲鱼的逆波兰算法，发现其中有很大的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[MAX_BUFF_VOLUMN] = {0};
        char *p = buff;
        int i = 0;
        T d, e;
        while(*p != '\0')
        {
            // filter digit
            while(isdigit(*p) || *p == '.')
            {
                str[i++] = *p;
                // use to end
                str[i] = '\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[64] = {0};
    char buff[32] = "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;
}

实例的实现