博客

数据结构中缀表达式转换为后缀表达式并求值

1 中缀表达式转换为后缀表达式并求值 (100分)

把题目给出中缀表达式转换为后缀表达式输出，并求后缀表达式的值。为简单起见，我们约定：1、输入的中缀表达式一定是合法的，并且只含数字，四种运算符+、-、*、/和小括号；2、运算数都是一位正整数(1～9)；3、输入的中缀表达式不超过20个字符；4、除法运算的结果仍然是正整数。

输入格式:

输入的第一行是一个正整数 N ，表示以下有 N 行。每行是一个中缀表达式。为简单起见，我们约定：1、输入的中缀表达式一定是合法的，并且只含数字，四种运算符+、-、*、/和小括号；2、运算数都是一位正整数(1～9)；3、输入的中缀表达式不超过20个字符；4、除法运算的结果仍然是正整数。

输出格式:

输出每行中缀表达式所对应后缀表达式，隔一个空格之后，输出该后缀表达式计算之后得到的值。

输入样例:

在这里给出一组输入。例如：

6

2+4

3+2

7

2

(4+6)

(5/2+4)

5+2

(3+5)

(7-2)/4

5*(8-(3+2))

输出样例:

在这里给出相应的输出。例如：

24+ 6

327*+ 17

246+* 20

52/4+5*2+ 32

35+72-

4/ 10

5832±

15

// An highlighted block
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct _nodechar
{
    char data;
    struct _nodechar *next;
} nodechar;

typedef struct _stackchar
{
    int size;
    nodechar *top;
} stackchar;

//创建
stackchar *createStackchar(void);
//入栈
void pushchar(stackchar* pStack, char x);
//出栈 #include <ctype.h>
void popchar(stackchar* pStack);
//获取栈顶元素
char topchar(stackchar* pStack);
//判空
bool emptychar(stackchar* pStack);
//销毁
void destroyStackchar(stackchar* pStack);

int getPriority(char op);

typedef struct _nodeint
{
    int data;
    struct _nodeint *next;
} nodeint;

typedef struct _stackint
{
    int size;
    nodeint *top;
} stackint;

//创建
stackint *createStackint(void);
//入栈
void pushint(stackint* pStack, int x);
//出栈
void popint(stackint* pStack);
//获取栈顶元素
int topint(stackint* pStack);
//判空
bool emptyint(stackint* pStack);
//销毁
void destroyStackint(stackint* pStack);

int calucalte(int op1, char op, int op2);

int main(void)
{
    int n;
    scanf("%d", &n);
    while(n--)
    {
        char infix[21], postfix[21] = "\0";
        int index = 0;
        scanf("%s", infix);
        stackchar *pStackchar = createStackchar();
        for(int i = 0; infix[i] != '\0'; i++)
        {
            if(infix[i] >= '0' && infix[i] <= '9')
            {
                postfix[index++] = infix[i];
            }
            else if(infix[i] == '(')
            {
                pushchar(pStackchar, infix[i]);
            }
            else if(infix[i] == ')')
            {
                char c = topchar(pStackchar);
                popchar(pStackchar);
                while(c != '(')
                {
                    postfix[index++] = c;
                    c = topchar(pStackchar);
                    popchar(pStackchar);
                }
            }
            else
            {
                if(emptychar(pStackchar) || getPriority(infix[i]) >getPriority(topchar(pStackchar)))
                {
                    pushchar(pStackchar, infix[i]);
                }
                else
                {
                    while(!emptychar(pStackchar) && getPriority(infix[i]) <= getPriority(topchar(pStackchar)))
                    {
                        char c = topchar(pStackchar);
                        popchar(pStackchar);
                        postfix[index++] = c;
                    }
                    pushchar(pStackchar, infix[i]);
                }
            }
        }
        while(!emptychar(pStackchar))
        {
            char c = topchar(pStackchar);
            popchar(pStackchar);
            postfix[index++] = c;
        }
        printf("%s", postfix);
        destroyStackchar(pStackchar);
        stackint *pStackint = createStackint();
        for(int i = 0; postfix[i] != '\0'; i++)
        {
            if(postfix[i] >= '0' && postfix[i] <= '9')
            {
                int m = postfix[i] - '0';
                pushint(pStackint, m);
            }
            else
            {
                char op = postfix[i];
                int op2, op1;
                op2 = topint(pStackint);
                popint(pStackint);
                op1 = topint(pStackint);
                popint(pStackint);
                pushint(pStackint, calucalte(op1, op, op2));
            }
        }
        int answer = topint(pStackint);
        printf(" %d\n", answer);
        popint(pStackint);
        destroyStackint(pStackint);
    }
    return 0;
}

int getPriority(char op)
{
    if(op == '+' || op =='-')
        return 1;
    if(op == '*' || op == '/')
        return 2;
    return 0;
}

int calucalte(int op1, char op, int op2)
{
    switch(op)
    {
    case '+':
        return op1 + op2;
        break;
    case '-':
        return op1 - op2;
        break;
    case '*':
        return op1 * op2;
        break;
    case '/':
        return op1 / op2;
        break;
    }
    return 0;
}
//创建
stackchar *createStackchar(void)
{
    stackchar* p = (stackchar*)malloc(sizeof(stackchar));
    p->size = 0;
    p->top = NULL;
    return p;
}
//入栈
void pushchar(stackchar* pStack, char x)
{
    nodechar *t = (nodechar*)malloc(sizeof(nodechar));
    t->data = x;
    t->next = pStack->top;
    pStack->top = t;
    pStack->size++;
}
//出栈
void popchar(stackchar* pStack)
{
    nodechar *t = pStack->top;
    pStack->top = t->next;
    free(t);
    pStack->size--;
}
//获取栈顶元素
char topchar(stackchar* pStack)
{
    return pStack->top->data;
}
//判空
bool emptychar(stackchar* pStack)
{
    //return pStack->size == 0;
    return pStack->top == NULL;
}
//销毁
void destroyStackchar(stackchar* pStack)
{
    while (!emptychar(pStack))
    {
        popchar(pStack);
    }
    free(pStack);
}

stackint *createStackint(void)
{
    stackint* p = (stackint*)malloc(sizeof(stackint));
    p->size = 0;
    p->top = NULL;
    return p;
}
//入栈
void pushint(stackint* pStack, int x)
{
    nodeint *t = (nodeint*)malloc(sizeof(nodeint));
    t->data = x;
    t->next = pStack->top;
    pStack->top = t;
    pStack->size++;
}
//出栈
void popint(stackint* pStack)
{
    nodeint *t = pStack->top;
    pStack->top = t->next;
    free(t);
    pStack->size--;
}
//获取栈顶元素
int topint(stackint* pStack)
{
    return pStack->top->data;
}
//判空
bool emptyint(stackint* pStack)
{
    //return pStack->size == 0;
    return pStack->top == NULL;
}
//销毁
void destroyStackint(stackint* pStack)
{
    while (!emptyint(pStack))
    {
        popint(pStack);
    }
    free(pStack);
}