HZOJ-266：表达式计算

题目描述

​ 给出一个表达式,其中运算符仅包含 +,-,*,/,^ 要求求出表达式的最终值。

​ 数据可能会出现括号情况，还有可能出现多余括号情况，忽略多余括号，正常计算即可；

​ 数据保证不会出现大于 max long int 的数据；

​ 数据可能会出现负数情况，幂次不可能为负数，除法采用向 0 取整。

​ 注意：−9 和 +9 分别代表负数和正数的 9

---

输入

​ 共一行，即为表达式。表达式长度不会超过1000.

输出

​ 共一行，既为表达式算出的结果。

---

样例输入1

(2+2)^(1+1)

样例输出1

16

样例输入2

9/-9

样例输出2

-1

---

数据规模与约定

​ 时间限制：1 s

​ 内存限制：256 M

​ 100% 的数据保证 数据合法

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define MAX 1000void weight(char* str, int* wei, int n) {int c = 0;for (int i = 0; i < n; i++) {switch (str[i]) {case '+': wei[i] = c + 1; break;case '-': {if (i == 0 || wei[i - 1] > 0) wei[i] = 0;else wei[i] = c + 1;break;}case '*':case '/': wei[i] = c + 2; break;case '^': wei[i] = c + 3; break;case '(': c += 10, wei[i] = -1; break;case ')': c -= 10, wei[i] = -1; break;default: wei[i] = 0;}}return;
}int calc(char* str, int* wei, int l, int r) {int ind = -1;for (int i = r - 1; i >= l; i--) {if (wei[i] > 0) {if (ind == -1 || wei[i] < wei[ind]) {ind = i;}}}if (ind == -1) {int c = 0, flag = 0;for (int i = l; i < r; i++) {if (wei[i] == 0) {if (str[i] == '-') flag = 1;else {int n = str[i] - '0';c = c * 10 + n;}}}return flag == 1 ? -c : c;}int a = calc(str, wei, l, ind);int b = calc(str, wei, ind + 1, r);switch (str[ind]) {case '+': return a + b;case '-': return a - b;case '*': return a * b;case '/': return a / b;case '^': return pow(a, b);}
}int main() {char str[MAX] = { 0 };gets(str);int len = strlen(str);int* wei = (int*)malloc(sizeof(int) * len);weight(str, wei, len);printf("%d", calc(str, wei, 0, len));free(wei);return 0;
}