数据结构-栈\队列：中缀表达式转后缀表达式并计算

刚开始接触C的语法，十分不熟悉，用中缀转后缀来练练手。
代码写的比较粗糙，还有待优化，实现了初步功能。
默认输入都是正确的，没有做错误处理，默认为全部整数运算。

算法核心

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <bits/stdc++.h>

using namespace std;

// 定义操作符的优先级
int priority(char opera) {
    int priorit = -1;
    switch (opera) {
        case '+':
        case '-':
            priorit = 1;
            break;
        case '*':
        case '/':
            priorit = 2;
            break;
        case '(':
            priorit = 0;
            break;
        default:
            break;
    }
    return priorit;
}

// 判断当前元素是否是操作符
bool isOper(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/';
}
// 计算
bool calculateVal(char oper, int &num1, int num2) {
    switch (oper) {
        case '+':
            num1 += num2;
            break;
        case '-':
            num1 -= num2;
            break;
        case '*':
            num1 *= num2;
            break;
        case '/':
            if (0 == num2) {
                printf("除数不为0");
                return false;
            }
            num1 /= num2;
            break;
        default:
            return false;
    }
    return true;
}
/**
 * 中缀表达式转后缀
 * @param infix
 * @param suffix
 * @return
 */
bool infix2Suffix(string infix, string &suffix) {
    int len = infix.length();
    if (len == 0) return false;
    int j = 0;
    stack<char> oStack;
    for (int i = 0; i < len; i++) {
        if ('(' == infix[i]) {
            oStack.push('('); // 左括号直接入栈
        } else if (')' == infix[i]) {
            // 右括号
            while (oStack.top() != '(') {
                // 将左括号前的运算符全部出栈
                suffix += oStack.top();
                oStack.pop();
            }
            oStack.pop(); // 左括号出栈
        } else if (isdigit(infix[i])) {
            // 数字
            while (isdigit(infix[i])) {
                // 一直读到非数字的位置
                suffix += infix[i++];
            }
            i--;
            suffix += ' '; // 插入空格区分多个连续的数字
        } else if (isOper(infix[i])) {
            // 操作符
            while (!oStack.empty() && priority(infix[i]) <= priority(oStack.top())) {
                // 弹出所有优先级高于等于该操作符的操作符
                suffix += oStack.top();
                oStack.pop();
            }
            oStack.push(infix[i]);
        }
    }
    while (!oStack.empty()) { // 弹出剩余的操作符写入后缀表达式
        suffix += oStack.top();
        oStack.pop();
    }
}

bool calculateSuffix(string suffix) {
    int len = suffix.length();
    if (len == 0) return false;
    stack<int> nStack; // 操作数栈
    int num2 = 0; // 用来拼接当前连续数字
    int num1 = 0;
    for (int i = 0; i < len; ++i) {
        if (' ' == suffix[i]) {
            // 空格直接略过
            continue;
        } else if (isdigit(suffix[i])) {
            while (isdigit(suffix[i])) {
                // 将字符串中连续的单个数字拼成完整的整数
                num2 = num2 * 10 + (suffix[i++] - '0'); // char 转 int
            }
            nStack.push(num2); // 将整数压入栈中
            i--; // i 复位
            num2 = 0; // tempNum 复位，用以下次的拼接
        } else if (isOper(suffix[i])) {
            // 遇到操作符，弹出两个操作数
            num2 = nStack.top();
            nStack.pop();
            num1 = nStack.top();
            nStack.pop();
            // 计算两个数
            calculateVal(suffix[i], num1, num2);
            // 将结果重新压入栈
            nStack.push(num1);
            num2 = 0; // 复位
        }
    }
    // 计算完成后打印结果
    cout << "后缀表达式的计算结果为：" << suffix << " = " << nStack.top() << endl;
}

int main() {
    string infixString; // 前缀表达式
    string suffixString; // 后缀表达式
    while (cin >> infixString) { // 循环输入
        infix2Suffix(infixString, suffixString);
        cout << "中缀表达式转后缀表达式为： " << infixString << " = " << suffixString << endl;
        calculateSuffix(suffixString);
        suffixString.clear();
//        printf("中缀表达式： %s 转后缀为： %s",infixString,suffixString);
    }

    return 0;
}

结果

image.png

全部用栈实现：
中缀转后缀使用了一个单链表栈；
后缀表达式计算使用了一个顺序栈

//
// Created by zhixiang.xiao on 2020/9/8.
//

/**
 * 将中缀表达式转变成后缀表达式：
 *      1. 定义运算符优先级
 *      2. 数字直接输出
 *      3. 遇到操作符：
 *          s1. 如果栈为空，直接入栈；
 *          s2. 如果该操作符优先级大于栈顶操作符，直接入栈；
 *          s3. 如果该操作符优先级低于栈顶，将栈内高（同）优先级操作符出栈，直到栈空或者遇见左括号
 *
 * 运算后缀表达式：
 *  1. 遇到操作数入栈
 *  2. 遇到操作符弹出两个操作数进行计算
 *
 */

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>

#define NnmStackMaxSize 20

// 操作符栈节点
typedef struct ONode {
    char data;
    ONode *next;
} ONode, *OStack;

// 初始化链栈 （带头节点）
bool initOStack(OStack &stack) {
    stack = (ONode *) malloc(sizeof(ONode));
    if (NULL == stack) return false;
    stack->next = NULL;
}

// 判空
bool isOStackEmpty(OStack stack) {
    return NULL == stack->next;
}

// 入栈：头插法插入元素
bool push2OStack(OStack &stack, char elem) {
    // 将新元素放入一个节点
    ONode *newNode = (ONode *) malloc(sizeof(ONode));
    if (NULL == newNode) return false;
    newNode->data = elem;
    // 在头部插入该节点
    newNode->next = stack->next;
    stack->next = newNode;
    return true;
}

// 出栈：取出并移除链栈第一个节点
bool popOStack(OStack &stack, char &val) {
    if (isOStackEmpty(stack)) return false; // 栈空
    ONode *node = stack->next;
    val = node->data;
    stack->next = node->next;
    free(node); // 释放该节点
    return true;
}

// 读取栈顶
bool getTopOStack(OStack stack, char &val) {
    if (isOStackEmpty(stack)) return false;
    val = stack->next->data;    // 栈顶元素
    return true;
}

// 操作数顺序栈节点
typedef struct {
    int data[NnmStackMaxSize];
    int top; // 栈顶指针
} NumStack;

// 初始化顺序栈
void initNumStack(NumStack &numStack) {
    numStack.top = -1; // 初试栈顶指向 -1
}

// 判空
bool isNumStackEmpty(NumStack numStack) {
    return numStack.top == -1;
}

// 判满
bool isNumStackFull(NumStack numStack) {
    return NnmStackMaxSize == numStack.top + 1;
}

// 入栈：
bool push2NumStack(NumStack &numStack, int elem) {
    if (isNumStackFull(numStack)) return false; // 栈满
    numStack.data[++numStack.top] = elem; // 栈顶插入元素
    return true;
}

// 出栈
bool popNumStack(NumStack &numStack, int &val) {
    if (isNumStackEmpty(numStack)) return false; // 栈空
    val = numStack.data[numStack.top--];
    return true;
}

// 读取栈顶元素
bool getTopNumStack(NumStack numStack, int &val) {
    if (isNumStackEmpty(numStack)) return false; // 栈满
    val = numStack.data[numStack.top];
    return true;
}

// 定义操作符的优先级
int getPriorityOfOperator(char opera) {
    int priorit = -1;
    switch (opera) {
        case '+':
        case '-':
            priorit = 0;
            break;
        case '*':
        case '/':
            priorit = 1;
            break;
        case '(':
            priorit = 2;
            break;
        default:
            break;
    }
    return priorit;
}

// 判断当前元素是否是操作符
bool isOperator(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/' || c == '(' || c == ')';
}

/**
 * 中缀表达式转后缀表达式
 * @param infixStr
 * @param suffixStr
 * @return
 */
bool changeInfix2Suffix(char *infixStr, char *suffixStr) {
    if (NULL == infixStr || !strlen(infixStr)) { // 字符串为空或长度为0
        printf("infix expression is empty!");
        return false;
    }
    // 定义一个操作符栈用来存放操作符
    OStack oStack;
    initOStack(oStack);

    int len = strlen(infixStr); // 字符串长度
    int curNum = 0; // 读取的数字
    int k = 0; // 后缀表达式的下标
    int i = 0; // 当前读取的中缀表达式的下标
    char tempChar; // 临时存储当前的字符
    while (infixStr[i] != '\0') {
        if (infixStr[i] == ' ' || infixStr[i] == '\t') {
            i++;
            continue; // 略过空格和制表符
        } else if (isdigit(infixStr[i])) {
            // 如果当前读取的是数字
            while (isdigit(infixStr[i])) {
                // 将连续的数字直接输出到后缀表达式中
                suffixStr[k++] = infixStr[i++];
            }
            // 输入一个完整的数据后插入一个空格用来区分两个数据
            suffixStr[k++] = ' ';
            continue;
        } else if ('(' == infixStr[i]) {
            // 如果是左括号直接入栈
            push2OStack(oStack, infixStr[i++]);
        } else if (')' == infixStr[i]) {
            // 如果是右括号，将栈内元素出栈直至左括号
            i++;
            // 查询当前栈顶元素是否为左括号
            while (getTopOStack(oStack, tempChar) && tempChar != '(') {
                // 如果当前栈顶不是左括号，出栈并存入后缀表达式
                popOStack(oStack, tempChar); // 出栈
                suffixStr[k++] = tempChar;
            }
            // 将其他操作符存入后缀表达式之后取出当前栈顶的左括号
            popOStack(oStack, tempChar);
            continue;
        } else if (isOperator(infixStr[i])) {// 是其他操作符
            getTopOStack(oStack, tempChar); // 获取当前栈顶操作符
            if (isOStackEmpty(oStack) ||
                getPriorityOfOperator(tempChar) < getPriorityOfOperator(infixStr[i])
                || tempChar == '(') {
                // 如果栈为空，或者栈顶操作符的优先级低于当前操作符的优先级
                // 直接入栈
                push2OStack(oStack, infixStr[i++]);
            } else {
                // 当前栈顶操作符的优先级高于或者等于当前操作符的优先级
                // 一直从栈中弹出操作符
                do {
                    getTopOStack(oStack, tempChar); // 获取栈顶操作符
                    if (getPriorityOfOperator(tempChar) >= getPriorityOfOperator(infixStr[i])
                        && tempChar != '(') {
                        // 栈不为空，栈顶优先级高于或等于当前操作符
                        popOStack(oStack, tempChar); // 出栈
                        suffixStr[k++] = tempChar; // 放入后缀表达式
                    }
                } while (!isOStackEmpty(oStack) &&
                         getPriorityOfOperator(tempChar) >= getPriorityOfOperator(infixStr[i])
                         && tempChar != '(');
                push2OStack(oStack, infixStr[i++]); // 当前操作符入栈
            }
        }
    }
    // 读取完字符之后将操作符栈中的操作符依次放入后缀表达式中
    while (!isOStackEmpty(oStack)) {
        popOStack(oStack, tempChar);
        suffixStr[k++] = tempChar;
    }
}

// 计算
bool calculateVal(char oper, int num1, int num2, int &val) {
    switch (oper) {
        case '+':
            val = num1 + num2;break;
        case '-':
            val = num1 - num2;break;
        case '*':
            val = num1*num2;break;
        case '/':
            if (0==num2){
                printf("除数不为0");
                return false;
            }
            val = num1 / num2;break;
        default:return false;
    }
    return true;
}

// 计算后缀表达式
bool calculateSuffixStr(char *suffixStr, int &val) {
    if (NULL == suffixStr || !strlen(suffixStr)) { // 字符串为空或长度为0
        printf("suffix expression is empty!");
        return false;
    }
    // 定义操作数顺序栈
    NumStack numStack;
    initNumStack(numStack);
    int i = 0; // 当前 表达式读取到的下标
    int tempNum = 0; // 存储数字
    int num1, num2; // 两个操作数
    while (suffixStr[i] != '\0') {
        if (suffixStr[i] == ' ' || suffixStr[i] == '\t') {
            i++;
//            continue; // 略过空格和制表符
        } else if (isdigit(suffixStr[i])) {
            // 如果当前读取的是数字
            while (isdigit(suffixStr[i])) {
                // 将连续的数字组成完整的整数
                tempNum = tempNum * 10 + (suffixStr[i] - '0'); // 字符转数字
                i++;
            }
            // 将一个完整的数字存入操作数栈
            push2NumStack(numStack, tempNum);
            tempNum = 0;  // 归零
        } else if (isOperator(suffixStr[i])) {
            // 是操作符，则从栈中取两个操作数
            popNumStack(numStack, num2);
            popNumStack(numStack, num1);
            // 计算
            calculateVal(suffixStr[i],num1,num2,tempNum);
            // 将结果重新入栈
            push2NumStack(numStack,tempNum);
            tempNum = 0;
            i++;
        }
    }
    popNumStack(numStack,val);
    return true;
}

int main() {
    //不要char* infixStr，然后gets(p)，这是错误的，因为p没有指向有效的内存
    char infixStr[100]; // 中缀表达式字符串
    gets(infixStr); // 从键盘读入表达式，会包含空格之类的字符
    char suffixStr[100]; // 后缀表达式
    // 中缀表达式转后缀表达式
    changeInfix2Suffix(infixStr, suffixStr);
    printf("%s\n", suffixStr);
    // 计算后缀表达式
    int val;
    calculateSuffixStr(suffixStr,val);
    printf("%s = %s = %d",infixStr,suffixStr,val);

    return 0;
}

计算结果

image.png

参考文章：
C语言 基本输入输出函数
C语言字符串函数