前缀、后缀，中缀表达式

Calendar October 23, 2023
数据结构

中缀表达式#

中缀表达式就是我们通常所写的表达式,如:1+2*3、1+(2+3)*4-5、1+2*(3+4*(5+6)) 等等。

后缀表达式及其求值方法#

后缀表达式又称为逆波兰表达式,它的特点是运算符在操作数的后面,如:123*+、123+4*+5-、123456+*+*+ 等等。

后缀表达式的求值方法#

后缀表达式的求值方法是:从左到右遍历表达式的每个数字和符号,遇到是数字就进栈,遇到是符号,就将处于栈顶两个数字出栈,进行运算,运算结果进栈,一直到最终获得结果。

例如:123*+ 的求值过程如下:

读入字符当前栈说明
11读入 1,进栈
21 2读入 2,进栈
31 2 3读入 3,进栈
*1 6读入 *,出栈 3 和 2,计算 2 * 3 = 6,将 6 进栈
+7读入 +,出栈 6 和 1,计算 1 + 6 = 7,将 7 进栈

C++ 实现后缀表达式的求值#

用C++实现后缀表达式的求值。要求有简单的控制台UI,并且要对用户的危险行为进行检查和警告。控制台输出的语句要求是中英文对照,并且在用户进行错误操作的时候告知他进行了什么错误操作。

#include <iostream>
#include <stack>
#include <string>
#include <sstream>
#include <cctype>

using namespace std;

// 函数声明
bool isOperator(char c);
double performOperation(char op, double operand1, double operand2);
bool evaluatePostfixExpression(const string& postfix, double& result);

int main() {
    cout << "欢迎使用后缀表达式计算器!" << endl;
    cout << "请输入一个后缀表达式,使用空格分隔操作数和操作符,输入'q'退出:" << endl;

    while (true) {
        string input;
        getline(cin, input);

        if (input == "q") {
            cout << "感谢使用后缀表达式计算器,再见!" << endl;
            break;
        }

        // 检查输入中的非法字符
        bool validInput = true;
        for (char c : input) {
            if (!isspace(c) && !isdigit(c) && !isOperator(c)) {
                validInput = false;
                cout << "错误:输入包含非法字符 '" << c << "'" << endl;
                break;
            }
        }

        if (validInput) {
            double result;
            if (evaluatePostfixExpression(input, result)) {
                cout << "结果: " << result << endl;
            }
            else {
                cout << "错误:无效的后缀表达式" << endl;
            }
        }

        cout << "请输入另一个后缀表达式,或输入'q'退出:" << endl;
    }

    return 0;
}

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

double performOperation(char op, double operand1, double operand2) {
    switch (op) {
    case '+':
        return operand1 + operand2;
    case '-':
        return operand1 - operand2;
    case '*':
        return operand1 * operand2;
    case '/':
        if (operand2 != 0) {
            return operand1 / operand2;
        }
        else {
            cout << "错误:除数不能为零" << endl;
            exit(1);
        }
    default:
        cout << "错误:未知的操作符 '" << op << "'" << endl;
        exit(1);
    }
}

bool evaluatePostfixExpression(const string& postfix, double& result) {
    stack<double> operandStack;

    istringstream iss(postfix);
    string token;
    while (iss >> token) {
        if (isdigit(token[0])) {
            double operand = stod(token);
            operandStack.push(operand);
        }
        else if (isOperator(token[0])) {
            if (operandStack.size() < 2) {
                cout << "错误:操作数不足" << endl;
                return false;
            }
            double operand2 = operandStack.top();
            operandStack.pop();
            double operand1 = operandStack.top();
            operandStack.pop();
            double result = performOperation(token[0], operand1, operand2);
            operandStack.push(result);
        }
        else {
            cout << "错误:无效的标记 '" << token << "'" << endl;
            return false;
        }
    }

    if (operandStack.size() == 1) {
        result = operandStack.top();
        return true;
    }
    else {
        cout << "错误:操作数不足或操作符过多" << endl;
        return false;
    }
}

C 实现后缀表达式的求值#

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

#define MAX_STACK_SIZE 100
#pragma warning(disable : 4996)

// 栈结构和操作
typedef struct {
    double data[MAX_STACK_SIZE];
    int top;
} Stack;

void initialize(Stack* stack) {
    stack->top = -1;
}

int isEmpty(Stack* stack) {
    return stack->top == -1;
}

void push(Stack* stack, double value) {
    if (stack->top < MAX_STACK_SIZE - 1) {
        stack->data[++stack->top] = value;
    }
    else {
        printf("错误:栈已满\n");
        exit(1);
    }
}

double pop(Stack* stack) {
    if (!isEmpty(stack)) {
        return stack->data[stack->top--];
    }
    else {
        printf("错误:栈为空\n");
        exit(1);
    }
}

// 函数声明
int isOperator(char c);
double performOperation(char op, double operand1, double operand2);
int evaluatePostfixExpression(const char* postfix, double* result);

int main() {
    printf("欢迎使用后缀表达式计算器!\n");
    printf("请输入一个后缀表达式,使用空格分隔操作数和操作符,输入'q'退出:\n");

    while (1) {
        char input[100];
        fgets(input, sizeof(input), stdin);
        input[strcspn(input, "\n")] = '\0'; // 去掉换行符

        if (strcmp(input, "q") == 0) {
            printf("感谢使用后缀表达式计算器,再见!\n");
            break;
        }

        // 检查输入中的非法字符
        int validInput = 1;
        for (int i = 0; input[i] != '\0'; i++) {
            if (!isspace(input[i]) && !isdigit(input[i]) && !isOperator(input[i])) {
                validInput = 0;
                printf("错误:输入包含非法字符 '%c'\n", input[i]);
                break;
            }
        }

        if (validInput) {
            double result;
            if (evaluatePostfixExpression(input, &result)) {
                printf("结果: %g\n", result);
            }
            else {
                printf("错误:无效的后缀表达式\n");
            }
        }

        printf("请输入另一个后缀表达式,或输入'q'退出:\n");
    }

    return 0;
}

int isOperator(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

double performOperation(char op, double operand1, double operand2) {
    switch (op) {
    case '+':
        return operand1 + operand2;
    case '-':
        return operand1 - operand2;
    case '*':
        return operand1 * operand2;
    case '/':
        if (operand2 != 0) {
            return operand1 / operand2;
        }
        else {
            printf("错误:除数不能为零\n");
            exit(1);
        }
    default:
        printf("错误:未知的操作符 '%c'\n", op);
        exit(1);
    }
}

int evaluatePostfixExpression(const char* postfix, double* result) {
    Stack operandStack;
    initialize(&operandStack);

    char* token = strtok((char*)postfix, " ");
    while (token != NULL) {
        if (isdigit(token[0])) {
            double operand = atof(token);
            push(&operandStack, operand);
        }
        else if (isOperator(token[0])) {
            if (operandStack.top < 1) {
                printf("错误:操作数不足\n");
                return 0;
            }
            double operand2 = pop(&operandStack);
            double operand1 = pop(&operandStack);
            double result = performOperation(token[0], operand1, operand2);
            push(&operandStack, result);
        }
        else {
            printf("错误:无效的标记 '%s'\n", token);
            return 0;
        }

        token = strtok(NULL, " ");
    }

    if (operandStack.top == 0) {
        *result = operandStack.data[0];
        return 1;
    }
    else {
        printf("错误:操作数不足或操作符过多\n");
        return 0;
    }
}

后缀表达式的转换方法(中缀转后缀)#

将中缀表达式转换为后缀表达式的方法是:从左到右遍历中缀表达式的每个数字和符号,若是数字就输出,若是符号,则判断其与栈顶符号的优先级,是右括号或优先级不高于栈顶符号(乘除优先加减)则栈顶元素依次出栈并输出,并将当前符号进栈,一直到最终输出后缀表达式为止。