C++表达式的值（中缀表达式）

Question

时间限制：1秒 内存限制：128M
题目描述
给定一个只包含加法和乘法的算术表达式，请你编程计算表达式的值。

输入描述
输入仅有一行，为需要你计算的表达式，表达式中只包含数字、加法运算符 + 和乘法运算符 * ，且没有括号，所有参与运算的数字均为0 到 2^31-1 之间的整数。输入数据保证这一行只有 0~ 9、+、*这 12 种字符。

输出描述
输出只有一行，包含一个整数，表示这个表达式的值。

样例
输入
1+1*3+4
输出
8

提示
对于 30%的数据，0≤表达式中加法运算符和乘法运算符的总数≤100；
对于 80%的数据，0≤表达式中加法运算符和乘法运算符的总数≤1000；
对于 100%的数据，0≤表达式中加法运算符和乘法运算符的总数≤100000。

// 表达式求值
// 将中缀表达式转成后缀表达式
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
using namespace std;

char a[100005];      // 存储后缀表达式
int in=0;

// 定义栈
char stack1[100005]; // 存储操作符
int top1=-1;

// 定义栈
int stack2[100005]; // 存储后缀表达式的数字及计算得到的数字
int top2=-1;


int main() {
    string s;
    cin>>s;
    
    // 遍历中缀表达式
    for(int i=0; i<s.length(); i++) {
        // 1、操作符 2、操作数
        if(s[i]>='0'&& s[i]<='9') {
            a[in++]=s[i];
            while(s[i+1]>='0' && s[i+1]<='9') {
                a[in++]=s[i+1];
                i++;
            }
            a[in++]=' ';
        } else {
            // 1.1 栈空，操作符进栈
            if(top1==-1) {
                stack1[++top1]=s[i];
            } else {
                // 1.2 优先级大于栈顶操作符，操作符进栈
                if(stack1[top1]='+' && s[i]=='*') {
                    stack1[++top1]=s[i];
                }
                // 1.3 优先级不大于栈顶操作符，栈顶操作符依次出栈，操作符进栈
                if(s[i]=='+') {
                    while(top1!=-1) {
                        a[in++]=stack1[top1--];
                        a[in++]=' ';
                    }
                    stack1[++top1]=s[i];
                }
            }
        }
    }

    // 栈不为空，操作符放依次出栈输出
    while(top1!=-1) {
        a[in++]=stack1[top1--];
        a[in++]=' ';
    }

    // cout<<strlen(a)<<endl; // 6

    // 遍历后缀表达式
    for(int i=0; i<strlen(a); i++) {
        // 1、操作符 2、操作数
        if(a[i]=='+') {
            // 1.1 元素出栈
            int r=stack2[top2--]; // 栈顶元素作为右操作数
            int l=stack2[top2--]; // 栈顶元素作为左操作数
            // 1.2 结果入栈
            int res=l+r;
            stack2[++top2]=res;
        } else if(a[i]=='*') {
            // 1.1 元素出栈
            int r=stack2[top2--]; // 栈顶元素作为右操作数
            int l=stack2[top2--]; // 栈顶元素作为左操作数
            // 1.2 结果入栈
            int res=l*r;
            stack2[++top2]=res;
        } else {
            // 2.1 获取数字
            int sum=0;
            while(a[i]!=' ') {
                sum=sum*10+a[i]-'0';
                i++;
            }
            // 2.2 数字入栈
            stack2[++top2]=sum;
        }
    }

        // 输出栈顶元素，即表达式的值
    cout<<stack2[top2]<<endl; // 3 答案错误 

    return 0;
}

理解过程：
由中缀表达式画出二叉树，最后做的运算在最顶层
后序遍历二叉树得到后缀表达式，前序遍历二叉树得到前缀表达式

    +
  +  4
1  *
  1  3

中缀表达式：1+1*3+4
后缀表达式：113*+4+
前缀表达式：++1*134

问题：
数组a用来存储后缀表达式，每个操作数、操作符中间用空格隔开

理论存储的是 {'1' ,' ', '1', ' ', '3', ' ', '*', ' ', '+', ' ', '4', ' ', '+', ' '} // strlen(a)=14
实际存储的是 {'1' ,' ', '1', ' ', '3', ' ', '\000', ' ', '\001', ' ', '4', ' ', '+', ' '} // strlen(a)=6

不知道为什么本应该存储 * 变成了 '\000'，存储 + 变成了 '\001' ？？
Dev C++ Debug，一开始栈空，stack1存的是 +，当 * 进栈的时候，原来栈中的 + 就变成了 '\000'，新入栈的 * 存成了 '\001' 这是什么原因导致的？？

Answer 1

你提到的错误可能是由于表达式中的操作符优先级处理不当，或者是在栈的操作中，未正确处理操作符导致存储或运算时出现了问题。问题关键可能出现在以下几个方面：

问题分析：

1. **栈顶操作符存储变成了\000和\001**：
   这可能是因为条件判断中，=符号被错误地使用。特别是你在处理优先级时，有一处错误：if(stack1[top1]='+' && s[i]=='*')，这里的=应为==（用于比较），而不是赋值操作符=。当使用=时，栈的值被意外修改，导致栈中的符号被错误地存储为\000或\001。

2. 操作符优先级处理问题：
   加法和乘法的优先级不同。乘法的优先级高于加法，所以在遇到乘法时应该优先处理，而加法则需要将之前的操作符出栈后再进行操作。这部分在代码逻辑里存在问题，需要修正。

修正建议：

• 修改条件判断：将if(stack1[top1]='+' && s[i]=='*')改为if(stack1[top1]=='+' && s[i]=='*')。
• 调整优先级处理逻辑：在处理中缀表达式时，应该考虑栈中的优先级规则，遇到乘法时，优先处理乘法操作。

改进后的代码：

#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
using namespace std;

char a[100005];      // 存储后缀表达式
int in=0;

// 定义栈
char stack1[100005]; // 存储操作符
int top1=-1;

// 定义栈
int stack2[100005]; // 存储后缀表达式的数字及计算得到的数字
int top2=-1;

// 判断操作符优先级
int priority(char op) {
    if (op == '*') return 2;
    if (op == '+') return 1;
    return 0;
}

int main() {
    string s;
    cin >> s;
    
    // 遍历中缀表达式
    for (int i = 0; i < s.length(); i++) {
        // 如果是数字
        if (s[i] >= '0' && s[i] <= '9') {
            a[in++] = s[i];
            while (s[i + 1] >= '0' && s[i + 1] <= '9') {
                a[in++] = s[i + 1];
                i++;
            }
            a[in++] = ' ';  // 数字后加一个空格
        } else { // 如果是操作符
            while (top1 != -1 && priority(stack1[top1]) >= priority(s[i])) {
                a[in++] = stack1[top1--];
                a[in++] = ' ';
            }
            stack1[++top1] = s[i];  // 操作符进栈
        }
    }

    // 把栈里的剩余操作符全部弹出
    while (top1 != -1) {
        a[in++] = stack1[top1--];
        a[in++] = ' ';
    }

    // 遍历后缀表达式
    for (int i = 0; i < strlen(a); i++) {
        if (a[i] == '+') {
            int r = stack2[top2--];
            int l = stack2[top2--];
            stack2[++top2] = l + r;
        } else if (a[i] == '*') {
            int r = stack2[top2--];
            int l = stack2[top2--];
            stack2[++top2] = l * r;
        } else if (a[i] >= '0' && a[i] <= '9') {
            int sum = 0;
            while (a[i] != ' ') {
                sum = sum * 10 + a[i] - '0';
                i++;
            }
            stack2[++top2] = sum;
        }
    }

    // 输出栈顶元素，即表达式的值
    cout << stack2[top2] << endl;

    return 0;
}

改进要点：

1. 优先级判断函数：priority函数用于返回操作符的优先级，确保乘法的优先级高于加法。
2. 栈操作符处理逻辑修正：当遇到新操作符时，检查栈中已有操作符的优先级，决定是否将其弹出。
3. 数字的处理：每次遇到数字时，将其解析并存入栈中，直到遇到操作符为止。

解释：

• 当你输入中缀表达式时，程序会先将其转换为后缀表达式，并使用栈来保存数字和操作符。操作符的优先级通过函数来判断，以确保乘法优先于加法。
• 生成后缀表达式后，通过栈的操作进行后缀表达式的计算。