题解 | 表达式求值

表达式求值

https://www.nowcoder.com/practice/c215ba61c8b1443b996351df929dc4d4

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 返回表达式的值
 * @param s string字符串 待计算的表达式
 * @return int整型
 */
#include <string.h>
#include<string.h>
#include<stdlib.h>
int solve(char* s ) {
    // write code here
    int i = 0;
    char pre[100000][4];
    for(int i=0;i<100000;i++){
        pre[i][3]='\0';
    }
    int flag_pre = 0;
    char stack[100000];
    int top = -1;
    int k=0;
    //int i_temp=0;
  //遍历中缀表达式
    while (s[i] != '\0') {
	  //当前字符为数字时，直接放入后缀表达式数组中
        if ((s[i] != '-' && s[i] != '(' && s[i] != '+' && s[i] != '*' && s[i] != ')')) {
            k=0;
		 //处理多位数的存放
            while(s[i] != '-' && s[i] != '(' && s[i] != '+' && s[i] != '*' && s[i] != ')'&&s[i] != '\0'){
                pre[flag_pre][k]=s[i];
                i++;
                k++;
            }
            flag_pre++;
        } 
	  //当前字符为'('时，直接压入操作符栈
	  else if (s[i] == '(') {
            top++;
            stack[top] = s[i];
            i++;
        }
	  //当当前字符为')'时，将操作符栈中从top到‘(’的操作符全都出栈，并存入后缀表达式数组中，'('也出栈，但不用存入后缀表达式数组中
	  else if (s[i] == ')') {
            while (stack[top] != '(') {
                pre[flag_pre][0] = stack[top];
                top--;
                flag_pre++;
            }
            top--;
            i++;
        }
	  //当当前字符为运算符号时，当当前操作符的优先级小于操作符栈栈顶操作符的优先级时，将栈顶的操作符出栈并放入后缀表达式数组中，直到当前操作符优先级大于栈顶操作符优先级时，将当前操作符压入栈中。
	  else if (stack[top] == '*' || (stack[top] == '+' && s[i] == '+') ||
                   (stack[top] == '+' && s[i] == '-') || (stack[top] == '-' && s[i] == '+') ||
                   (stack[top] == '-' && s[i] == '-')) {

            while (stack[top] == '*' || (stack[top] == '+' && s[i] == '+') ||
                    (stack[top] == '+' && s[i] == '-') || (stack[top] == '-' && s[i] == '+') ||
                    (stack[top] == '-' && s[i] == '-')) {
                pre[flag_pre][0] = stack[top];
                top--;
                flag_pre++;
            }
            top++;
            stack[top] = s[i];
            i++;
        }
	  //其他情况（当前栈为空或栈顶操作符为'('）也是直接入栈。
	  else {
            top++;
            stack[top] = s[i];
            i++;
        }
    }
  //最后将栈中留下的操作符全都出栈存入后缀表达式数组中
    while (top != -1) {
        pre[flag_pre][0] = stack[top];
        top--;
        flag_pre++;
    }
  //验证后缀表达式
    //for(int m=0;m<flag_pre;m++){
     //   printf("%s",pre[m]);
    //}  
    int end[10000];
    int top_end = -1;
    int temp = 0;
    int j = 0;    
    while (pre[j][0] != '\0') {
        if (pre[j][0] != '-' && pre[j][0] != '+' && pre[j][0] != '*') {
            top_end++;
            end[top_end] = atoi(pre[j]);
        }
        if (pre[j][0] == '+') {
            temp = end[top_end - 1] + end[top_end];
            top_end--;
            end[top_end] = temp;
        }
        if (pre[j][0] == '-') {
            temp = end[top_end - 1] - end[top_end];
            top_end--;
            end[top_end] = temp;
        }
        if (pre[j][0] == '*') {
            temp = end[top_end - 1] * end[top_end];
            top_end--;
            end[top_end] = temp;
        }
        j++;
    }
    return end[top_end];
}

本题的宏观思路为：将表达式转为后缀表达式后，再进行出入栈计算

中缀表达式转后缀表达式：

定义一个操作符栈stack（用数组表示）；定义一个top（栈顶指针）；定义一个用来存放后缀表达式的二维数组pre（数字有两三位数的情况，如果只用单纯的一维数组会将多位数看成几个一位数）；

然后遍历输入的中缀表达式，当当前字符为数字时，直接存入pre数组中（注意多位数数字的存放）；

当当前字符为'(',直接压入操作符栈中；

当当前字符为')'时，将操作符栈中从top到‘(’的操作符全都出栈，并存入后缀表达式数组中，'('也出栈，但不用存入后缀表达式数组中；

当当前字符为运算符号时，当当前操作符的优先级小于操作符栈栈顶操作符的优先级时，将栈顶的操作符出栈并放入后缀表达式数组中，直到当前操作符优先级大于栈顶操作符优先级时，将当前操作符压入栈中；

题解 | 表达式求值

全站热榜

创作者周榜