后缀表达式的计算算法问题

Question

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>
#include <stdbool.h>
#define ERROR 0
#define MAX 100
#include<iostream>
#include <string.h>
typedef struct                                          //用两个栈来别分存储运算数和运算符double char
{
    int top;
    double items[MAX];
} DoubleStack;

typedef struct {
    int top;
    char items[MAX];
} CharStack;

void pushDouble(DoubleStack *s, double item) {
    if (s->top < MAX) {
        s->top = s->top + 1;
        s->items[s->top] = item;
    } else {
        printf("栈已满。\n");
    }
}

double popDouble(DoubleStack *s) {
    if (s->top > 0) {
        return s->items[s->top--];
    } else {
        printf("栈为空。\n");
        return ERROR;
    }
}


void pushChar(CharStack *s, char item)             //入栈
 {
    if (s->top < MAX - 1) {
        s->top = s->top + 1;
         s->items[s->top] = item;

    } else {
        printf("栈已满。\n");
    }
}

char popChar(CharStack *s)                        //出栈
{
    if (s->top >= 0) {
        return s->items[s->top--];
    } else {
        printf("栈为空。\n");
        return '\0';
    }
}
char getTop(CharStack *stack) {
    if (stack->top >= 0) {
        return stack->items[stack->top];
    }
    return '\0'; // 返回空字符表示栈为空
}

int isoperator(char symbol)        //判断char栈中字符是否为运算符
{
    if (symbol == '+' || symbol == '-' || symbol == '*' || symbol == '/')
    {
        return 1; // 返回1表示是运算符
    }
    else
    {
        return 0; // 返回0表示不是运算符
    }
}

int precedence(char symbol)  //判断运算符的优先级  switch case函数
{
    switch (symbol) {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        default:
            return 0;
    }
}

double operate(double a, double b, char op)  //给出各运算符的运算操作
{
    switch (op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/':
            if (b != 0) {
                return a / b;
            } else {
                printf("错误：除数不能为零。\n");
                return ERROR;
    }

}
return 0;
}

int expression(char *expression) {
    int length = strlen(expression);
    int count_bracket = 0;
    int last_was_digit = 0;
    int has_operator = 0;
    int count_operator = 0;

    for (int i = 0; i < length; i++) {
        char ch = expression[i];

        if (isdigit(ch)) {
            last_was_digit = 1;
            has_operator = 0;
            count_operator--;
        } else if (isoperator(ch)) {
            has_operator = 1;
            count_operator++;
            last_was_digit = 0;
        } else if (ch == '(') {
            count_bracket++;
        } else if (ch == ')') {
            count_bracket--;
            if (count_bracket < 0) {
                printf("括号不匹配：右括号多于左括号\n");
                return 0;
            }
        } else {
            printf("非法字符：%c\n", ch);
            return 0;
        }


    }

    if (count_bracket != 0) {
        printf("括号不匹配：左括号多于右括号\n");
        return 0;
    } else if (!last_was_digit || count_operator > 0) {
        printf("算术表达式不合法\n");
        return 0;
    } else {
        printf("括号匹配正确，算术表达式合法\n");
        return 1;
    }
}




void infixToPostfix(const char *infix, char *postfix) {
    CharStack stack; //字符栈
    stack.top=-1;    //将其置空
    int i = 0, j = 0;  //i j分别用来遍历infix和postfix
    char c;

    while (infix[i] != '\0') //只要infxi[i]不为空
        {
        c = infix[i];
        if (isdigit(c))  //如果c为数字
        {
            postfix[j++] = c; // 直接输出数字到postfix
        }
        else if (isoperator(c)) //如果c为运算符
            {
            while (precedence(getTop(&stack)) >= precedence(c)) //判断此运算符的优先级   如果优先级小则把栈顶运算符弹出 进入postfix
            {
                postfix[j++] = popChar(&stack);
            }
            pushChar(&stack, c); //如果优先级大则入栈
        }
        else if (c == '(') {     //括号的入栈：遇见左括号直接入字符栈
            pushChar(&stack, c);
        }
        else if (c == ')') //当遇到右括号时
        {
            while (getTop(&stack) != '(') //在遇见左括号之前一直弹出栈中字符
                   {
                postfix[j++] = popChar(&stack);
            }
            popChar(&stack); // 最后弹出左括号
        }
        i++; //i进行循环+1
    }

    while (stack.top >= 0) //将栈里剩余的字符弹出
        {
        postfix[j++] = popChar(&stack);
    }
    postfix[j] = '\0'; // 结尾添加空字符
}
void evaluatePostfix(char* postfix, DoubleStack* stack)
 {
    char ch;
    double a, b, value;
    int i = 0;


    while (postfix[i] != '\0') {
        ch = postfix[i++];
        if (isdigit(ch))
            {
            pushDouble(stack,ch-'0' );
        }
        else if (isoperator(ch))
            {
            b = popDouble(stack);
            a = popDouble(stack);
            value = operate(a, b, ch);
            pushDouble(stack, value);
            printf("计算: %.2f %c %.2f = %.2f\n", a, ch, b, value);
        }
    }

}
int main()
{
    char infix[MAX], postfix[MAX];
    DoubleStack stack;
    stack.top = -1;

    printf("请输入算术表达式: ");
    scanf("%s", infix);

    if (expression(infix)) {
        infixToPostfix(infix, postfix);
        printf("后缀表达式: %s\n", postfix);
        evaluatePostfix(postfix, &stack);

        if (stack.top == 0) {
            printf("表达式的结果是: %.2f\n", popDouble(&stack));
        } else {
            printf("表达式无效或者栈操作错误。\n");
        }
    } else {
        printf("输入的表达式无效。\n");
    }

    return 0;
}

运行后遇见如图的问题

Answer 1

引自免费微信小程序：皆我百晓生

这个问题涉及到后缀表达式的计算，这是一种数学表达式处理方法，其中运算符放在它们右边的操作数之后。例如，"5+3*2"可以被转换成"5 3 2 *"。

对于后缀表达式，我们可以按照以下步骤进行计算：

1. 将所有非运算符的字符（数字和字母）存入一个栈。
2. 当遇到运算符时，从栈中弹出两个元素，并根据运算符执行相应的计算。
3. 然后将结果压回栈。
4. 重复以上过程直到整个表达式计算完成。

以下是C++实现这个算法的代码示例：

#include <iostream>
#include <vector>

using namespace std;

class ExpressionEvaluator {
public:
    vector<double> evaluate(const string& postfix) {
        vector<double> result;
        stack<double> operandStack;

        for (auto& ch : postfix) {
            if (isdigit(ch)) {
                operandStack.push(stod(string(1, ch)));
            } else if (ch == ' ') {
                continue;
            } else if (ch == '(') {
                operandStack.push(0);
            } else if (ch == ')') {
                while (!operandStack.empty()) {
                    double num = operandStack.top();
                    operandStack.pop();

                    double right = operandStack.empty() ? 0 : operandStack.top();
                    operandStack.pop();

                    double left = operandStack.empty() ? 0 : operandStack.top();
                    operandStack.pop();

                    result.push_back(compute(num, right, left));
                }
            } else {
                while (!operandStack.empty() && priority(ch) <= priority(operandStack.top())) {
                    double num = operandStack.top();
                    operandStack.pop();

                    double right = operandStack.empty() ? 0 : operandStack.top();
                    operandStack.pop();

                    double left = operandStack.empty() ? 0 : operandStack.top();
                    operandStack.pop();

                    result.push_back(compute(num, right, left));
                }
                operandStack.push(stod(string(1, ch)));
            }
        }

        while (!operandStack.empty()) {
            double num = operandStack.top();
            operandStack.pop();

            double right = operandStack.empty() ? 0 : operandStack.top();
            operandStack.pop();

            double left = operandStack.empty() ? 0 : operandStack.top();
            operandStack.pop();

            result.push_back(compute(num, right, left));
        }

        return result;
    }

private:
    bool operator==(const ExpressionEvaluator& other) const {
        return operands_ == other.operands_;
    }

    bool operator!=(const ExpressionEvaluator& other) const {
        return !(*this == other);
    }

    void push(const double& val) {
        operands_.push(val);
    }

    void pop() {
        operands_.pop();
    }

    vector<double> operands_;

    double compute(const double& a, const double& b, const double& c) {
        if (operands_[2] == 0) {
            return a + b + c;
        } else {
            return operands_[2] * (a + b + c);
        }
    }

    double priority(char ch) {
        if (ch == '^') {
            return 3;
        } else if (ch == '/' || ch == '*') {
            return 2;
        } else if (ch == '+' || ch == '-') {
            return 1;
        } else {
            return 0;
        }
    }
};

int main() {
    string expression;
    cout << "请输入算术表达式: ";
    getline(cin, expression);

    ExpressionEvaluator evaluator;
    vector<double> results = evaluator.evaluate(expression);

    for (const auto& result : results) {
        cout << result << endl;
    }

    return 0;
}

在这个代码中，我们首先定义了一个ExpressionEvaluator类，它包含了后缀表达式评估器的基本功能。然后，我们在main函数中创建了ExpressionEvaluator实例并调用了其evaluate函数来计算后缀表达式。最后，我们打印出了每个结果。

注意，这个代码没有考虑括号匹配问题，因此可能会导致错误的计算结果。如果你需要处理括号匹配问题，你需要修改evaluate函数，使其能识别和处理括号。