数据结构与算法之使用栈进行中缀表达式的计算

中缀表达式的计算(用栈计算)

用栈实现中缀表达式的计算：

1. 初始化两个栈，操作数栈和运算符栈
2. 若扫描到操作数，压入操作数栈
3. 若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈（期间也会弹出运算符，每当弹出一个运算符时，就需要在弹出两个操作数栈的栈顶元素并执行相应运算，运算结果在压回操作数栈）

耍巧做法：中缀转后缀+后缀表达式求值

#include "string.h"
#include "CharStack.h"
#include "IntStack.h"

void MidExpressionEvaluation(const char *str, int length, int *);

bool isSymbol(char c);

bool calculateBySymbol(int l, int r, char symbol, IntStack *stack);

bool leftCompareRight(char left, char right);

void rightBracketEvaluate(IntStack *intStack, CharStack *charStack, char *pop, char cur, int *left, int *right);

char symbolEvaluate(IntStack *intStack, CharStack *charStack, char *pop, char cur, int *left, int *right);


void twicePopIntStackACalculateAndPush(IntStack *intStack, const char *symbol, int *left, int *right);

bool leftCompareRight(char left, char right) {
    if (left == '+' || left == '-') {
        return false;
    }
    if (right == '*' || right == '/') {
        return false;
    }
    return true;
}


bool calculateBySymbol(int l, int r, char symbol, IntStack *stack) {
    int res = -9999;
    if (symbol == '+') {
        res = l + r;
    }
    if (symbol == '-') {
        res = l - r;
    }
    if (symbol == '*') {
        res = l * r;
    }
    if (symbol == '/') {
        res = l / r;
    }
    if (res != -9999) {
        pushInt(stack, res);
    }
    return true;
}


void MidExpressionEvaluation(const char *str, const int length, int *result) {
    //初始化两个栈
    IntStack *intStack = NULL;
    CharStack *charStack = NULL;
    initCharStack(&charStack);
    initIntStack(&intStack);
    char pop = '0';
    int left = 0;
    int right = 0;
    for (int i = 0; i < length; ++i) {
        char cur = str[i];
        if (cur == '(') {
            //左括号:直接入栈
            pushChar(charStack, cur);
            continue;
        }
        if (cur == ')') {
            //右括号:遇到")"则依次弹出栈内运算符并弹出数字栈进行计算，直到弹出"("为止。注意："("不加入后缀表达式。
            rightBracketEvaluate(intStack, charStack, &pop, cur, &left, &right);
            continue;
        }
        if (isSymbol(cur)) {
            //符号:依次弹出栈中优先级高于或等于当前运算符的所有运算符，并计算，若碰到"("或栈空则停止。之后在把当前运算符入栈
            pop = symbolEvaluate(intStack, charStack, &pop, cur, &left, &right);
            continue;
        } else {
            //数字:直接压入数字栈
            //减去码点表48位起始位
            int j = (int) (cur) - (int) ('0');
            pushInt(intStack, j);
            continue;
        }
    }
    //清栈处理
    while (!emptyCharStack(charStack)) {
        popChar(charStack, &pop);
        twicePopIntStackACalculateAndPush(intStack, &pop, &left, &right);
    }
    popInt(intStack, result);
}


char symbolEvaluate(IntStack *intStack, CharStack *charStack, char *pop, char cur, int *left, int *right) {
    while (true) {
        //碰到"("或栈空就停止，并把当前运算符压栈
        if (emptyCharStack(charStack)) {
            pushChar(charStack, cur);
            return (*pop);
        }
        locateCharElem(charStack, pop);
        if (*pop == '(') {
            pushChar(charStack, cur);
            return (*pop);
        }
        //弹出优先级高于或等于当前运算符的所有运算符，每次弹出就需要计算
        if (!leftCompareRight(cur, *pop)) {
            popChar(charStack, pop);
            twicePopIntStackACalculateAndPush(intStack, pop, left, right);
            continue;
        } else {
            pushChar(charStack, cur);
            return (*pop);
        }

    }
}


void rightBracketEvaluate(IntStack *intStack, CharStack *charStack, char *pop, char cur, int *left, int *right) {
    //todo:这段代码逻辑在理一下
    while (true) {
        popChar(charStack, pop);
        if ('(' == (*pop)) {
            break;
        } else {
            twicePopIntStackACalculateAndPush(intStack, pop, left, right);
        }
    }
}


void twicePopIntStackACalculateAndPush(IntStack *intStack, const char *symbol, int *left, int *right) {
    popInt(intStack, right);
    popInt(intStack, left);
    calculateBySymbol((*left), (*right), *symbol, intStack);
}

bool isSymbol(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

int main() {
    char *str = "1+2*(4-4)-5/1";
    int result = -1;
    MidExpressionEvaluation(str, (int) strlen(str), &result);
    printf("%dn", result);
    return 1;
}

为什么可以将char**“无伤”**转换为int型

1. 占用字节数比较：char
2. char就是一些特殊的码点单位的下标标识，底层还是使用的数字来进行标识

// 要点：强转后减去'0'所在码点位置即可
int j = (int) (cur) - (int) ('0');