《数据结构和算法》——逆波兰表达式

luciferzf

对于所求的中缀表达式，我们首先需要将其转换为后缀表达式，即将运算符写在作用的两个数的后面，然后将中缀表达式的输出作为后缀表达式计算程序的输入。
在一个中缀表达式，我们首先需要用栈来储存级别较高的运算符，如*，（等。在栈中只允许级别较高的运算符在级别较低的运算符上面，所以当读取到级别最低级别最低的“+”和“-”时就将栈中的运算符弹出至“（”或栈为空，“（”可以在任何运算符下面，一旦检测到“）”立刻将栈中的运算符弹出，至“（”的位置。当检测到“*”和“/”时则压入栈中。当输入完毕后将栈中所有符号弹出。


附上计算中缀表达式的算法：

#include<cstdio>
#include<cstdlib>
#include<math.h>
#include<iostream>
using namespace std;

typedef double elem;

class stack1
{
public:
        elem *top, *base;
        int stack_size;
};

class stack2
{
public:
        char *top, *base;
        int stack_size;
};

void Initial(stack1 *s)
{
        s->base = new elem[1000];
        s->top = s->base;
        s->stack_size = 0;
}
void Initial(stack2 *s)
{
        s->base = new char[1000];
        s->top = s->base;
        s->stack_size = 0;
}


void Push(stack1 *s,elem e)
{
        *(s->base) = e;
        s->base++;
        s->stack_size++;
}
void Push(stack2 *s, char e)
{
        *(s->base) = e;
        s->base++;
        s->stack_size++;
}

void Pop(stack1 *s,double *e)
{
        s->stack_size--;
        s->base--;
        *e = *(s->base);
}
void Pop(stack2 *s,char *e)
{
        s->base--;
        s->stack_size--;
        *e = *(s->base);
}


int main()
{
        stack1 s;
        stack2 r;
        char c;
        char str[20];
        elem d;
        Initial(&s);
        Initial(&r);

        printf("输入要计算的中缀表达式(以#结束，数字与符号之间用空格隔开)：");
        scanf_s("%c", &c);

        while (c!= '#')
        {
                int i = 0;
                while (isdigit(c) || c == '.')
                {
                        str[i++] = c;
                        str[i] = 0;
                        scanf_s("%c", &c);
                        if (i >= 20)printf("wrong,out of the limit!");
                        if (c == ' ')
                        {
                                d = atof(str);
                                Push(&s, d);
                        }
                }
                if (')' == c)
                {
                        char e;
                        do
                        {
                                Pop(&r, &e);
                                double a, b;
                                switch (e)
                                {
                                case '+':
                                        Pop(&s,&b);
                                        Pop(&s,&a);
                                        Push(&s, a + b);
                                        break;
                                case '-':
                                        Pop(&s, &b);
                                        Pop(&s, &a);
                                        Push(&s, a - b);
                                        break;
                                case '*':
                                        Pop(&s, &b);
                                        Pop(&s, &a);
                                        Push(&s, a * b);
                                        break;
                                case '/':
                                        Pop(&s, &b);
                                        Pop(&s, &a);
                                        Push(&s, a / b);
                                        break;
                                }
                        } while (r.stack_size&&'(' != e);
                }
                else if (c == '+' || c == '-')
                {
                        if (r.stack_size != 0)
                        {
                                char e;
                                do
                                {
                                        Pop(&r, &e);
                                        if ('(' == e)
                                        {
                                                Push(&r, e);
                                                break;
                                        }
                                        double a, b;
                                        switch (e)
                                        {
                                        case '+':
                                                Pop(&s, &b);
                                                Pop(&s, &a);
                                                Push(&s, a + b);
                                                break;
                                        case '-':
                                                Pop(&s, &b);
                                                Pop(&s, &a);
                                                Push(&s, a - b);
                                                break;
                                        case '*':
                                                Pop(&s, &b);
                                                Pop(&s, &a);
                                                Push(&s, a * b);
                                                break;
                                        case '/':
                                                Pop(&s, &b);
                                                Pop(&s, &a);
                                                Push(&s, a / b);
                                                break;
                                        }
                                } while (r.stack_size != 0 && e != '(');
                                Push(&r, c);
                        }
                        else if (r.stack_size == 0)
                        {
                                Push(&r, c);
                        }
                }
                else if ('*' == c || '/' == c||'('==c)
                {
                        Push(&r, c);
                }
                scanf_s("%c", &c);
        }
        while (r.stack_size != 0)
        {
                char e;
                double a, b;
                Pop(&r, &e);
                switch (e)
                {
                case '+':
                        Pop(&s, &b);
                        Pop(&s, &a);
                        Push(&s, a + b);
                        break;
                case '-':
                        Pop(&s, &b);
                        Pop(&s, &a);
                        Push(&s, a - b);
                        break;
                case '*':
                        Pop(&s, &b);
                        Pop(&s, &a);
                        Push(&s, a * b);
                        break;
                case '/':
                        Pop(&s, &b);
                        Pop(&s, &a);
                        Push(&s, a / b);
                        break;
                }
        }
        Pop(&s,&d);
        printf("answer is %.2f\n", d);
        system("PAUSE");
}