表达式求值

0.前言

对栈的应用，中缀表达式的直接求值。

1.代码实现

项目包含：

• main.cpp
• s.cpp
• s.h

main.cpp

#include "s.h"
int fun(int c, int d, char op) {
    switch (op) {
    case '-': return c - d;
    case '+': return c + d;
    case '*': return c * d;
    case '/': return c / d;
    case '%': return c % d;
    case '^': return pow(c, d);
    }
}
int calcu(char a[]) {
    int n = strlen(a);
    int c, d;
    stackp num, op;
    init(num);
    init(op);
    push(op, '#');

    for (int i = 0; i < n; i++) {
        if ('0' <= a[i] && a[i] <= '9') {
            push(num, a[i] - '0');
        }
        else {
            int x;
            gettop(op, x);

            //栈外的优先级高，进栈
            if (osp(a[i]) > isp(x)) {
                push(op, int(a[i]));
            }
            //栈内的优先级高，出栈
            else if (osp(a[i]) < isp(x)) {
                while (osp(a[i]) < isp(x)) {
                    pop(num, d);
                    pop(num, c);
                    push(num, fun(c, d, x));    //在pop op的时候计算

                    pop(op, x);
                    gettop(op, x);
                }
                if (osp(a[i]) > isp(x)) {
                    push(op, int(a[i]));
                }
            }
            if (osp(a[i]) == isp(x)) {
                pop(op, x);
                gettop(op, x);
            }
        }
    }

    //处理栈中剩下的op符
    int x;
    gettop(op, x);
    while (x != '#') {
        pop(num, d);
        pop(num, c);
        push(num, fun(c, d, x));

        pop(op, x);
        gettop(op, x);
    }
    gettop(num, x);
    return x;
}

void main() {
    stackp s;
    init(s);

    char a[100];
    printf("input the infix expression:\n");
    printf("!!!! dont take # \n");
    gets_s(a);
    printf("%s = %d", a, calcu(a));

    system("pause");
}

s.cpp

#include "s.h"

void init(stackp&s) {
    s = NULL;
}

int empty(const stackp& s) {
    return s == NULL;
}

//change s
void push(stackp & s, int x) {
    stackp p = new stack;
    if (p == NULL) {
        printf("error\n");
        exit(1);
    }
    p->data = x;
    p->next = s;
    s = p;
}

//change s
int pop(stackp& s, int &x) {
    if (empty(s)) return 0;
    stackp p = s;
    s = p->next;
    x = p->data;
    delete p;
    return 1;
}

int gettop(const stackp& s, int &x) {
    if (empty(s)) return 0;
    x = s->data;
    return 1;
}

int isp(char ch) {
    switch (ch) {
    case '#':
        return 0;
    case '(':
        return 1;
    case '^':
        return 7;
    case '*':
    case '/':
    case '%':
        return 5;
    case '+':
    case '-':
        return 3;
    case ')':
        return 8;
    default:
        printf("error");
        exit(-1);
    }
}

int osp(char ch) {
    switch (ch) {
    case '#':
        return 0;
    case '(':
        return 8;
    case '^':
        return 6;
    case '*':
    case '/':
    case '%':
        return 4;
    case '+':
    case '-':
        return 2;
    case ')':
        return 1;
    default:
        printf("error");
        exit(-1);
    }
}

s.h

#ifndef __S_H__
#define __S_H__
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#pragma warning(disable:4996)
#pragma warning(disable:4477)

typedef struct node {
    int data;
    struct node* next;
}stack, *stackp;

void init(stackp & s);
int empty(const stackp & s);
void push(stackp &s, int x);
int pop(stackp & s, int &x);
int gettop(const stackp & s, int & x);

int isp(char ch);
int osp(char ch);

#endif

2.小结

主要就是那个calcu函数，伪代码理解：

for i in infix_expression:
    if i是数字：
        放入数字栈
    else（i是操作符）：
        if 优先级高：
            放入运算符栈
        elif 优先级低：
            运算符栈pop，同时在数字栈中运算
            调整运算符栈
        if 优先级相等：
            调整运算符栈

for op in 运算符栈中的残留：
    数字栈中运算

return 数字栈中的唯一数字