四则运算表达式可以用表达式树表达,如下图后序遍历
现给你一个字符串,代表一个后序遍历形式的四则运算表达式,请计算出表达式的结果:(只输出整数部分)
注:除法只保留整数部分;5/4= 1
输入: 一个字符串,代表一个四则运算表达式,输入保证合法一定有计算结果,操作数是合法的整数,运算符只包含±*/;
输出: 一个整数 :范围 -2147483648 ~ 2147483647
样例: 9,3,5,-,2,*,+;
输出:5
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define BUF_LEN 50000
static int Calc(const char* input)
{
int i = 0;
int stack[BUF_LEN] = { 0 };
int top = 0;
char *savep = NULL;
char* p = strtok_s(input, ",", &savep);
while (p != NULL) {
if (strcmp(p, "+") == 0) {
stack[top - 2] = stack[top - 2] + stack[top - 1];
stack[top - 1] = 0;
top--;
p = strtok_s(NULL, ",", &savep);
continue;
}
if (strcmp(p, "-") == 0) {
stack[top - 2] = stack[top - 2] - stack[top - 1];
stack[top - 1] = 0;
top--;
p = strtok_s(NULL, ",", &savep);
continue;
}
if (strcmp(p, "*") == 0) {
stack[top - 2] = stack[top - 2] * stack[top - 1];
stack[top - 1] = 0;
top--;
p = strtok_s(NULL, ",", &savep);
continue;
}
if (strcmp(p, "/") == 0) {
stack[top - 2] = stack[top - 2] / stack[top - 1];
stack[top - 1] = 0;
top--;
p = strtok_s(NULL, ",", &savep);
continue;
}
(void)sscanf_s(p, "%d", &stack[top++]);
p = strtok_s(NULL, ",", &savep);
}
return stack[0];
}
int main(void)
{
static char buf[BUF_LEN];
if (get_s(buf, sizeof(buf)) == NULL) {
return -1;
}
int ret = Calc(buf);
(void)printf("%d", ret);
return 0;
}