怎样将字符串中的表达式计算出来？
输入一字符串，如"10+20-25",要怎么做才能计算出他的值。也就是说怎样将字符串转换成表达式？
[[it] 本帖最后由 ramble55 于 2008-11-18 23:02 编辑 [/it]]
main()
{
int a=10,b=20,c=25;
printf("%d",a+b-c);
}
2008-11-18 21:04
2008-11-18 22:42
2008-11-18 22:56
2008-11-18 22:57
2008-11-18 22:58
2008-11-19 02:33
程序代码：
#include <stdio.h>
#include <string.h>
#include <ctype.h>
/* 堆栈大小 */
#define STACK_MAX 100
/* 要求double达到的精度 */
#define IS_DOUBLE_ZERO(d) ((d) < 0.00000000001 && (d) > -0.00000000001)
/* 助手宏，检查当前堆栈包含元素数量 */
#define GET_STACK_SIZE(stack) (stack##_stack_top - stack##_stack + 1)
/* 助手宏，用于检查堆栈是否为空 */
#define IS_STACK_EMPTY(stack) (GET_STACK_SIZE(stack) <= 0)
/* 助手宏，用于检查堆栈是否已满 */
#define CHECK_STACK_OVERFLOW(stack) \
if (GET_STACK_SIZE(stack) >= STACK_MAX) \
return STATUS_STACK_OVERFLOW
/* 助手宏，用于每次的堆栈计算 */
#define CALC_OPT_IN_STACK() \
{ \
int ret = calc_opt_with_stack(opt_stack, &opt_stack_top, \
num_stack, &num_stack_top); \
if (ret != STATUS_OK) \
return ret; \
}
/* 状态枚举，由主函数及StackCalc返回 */
typedef enum status_type
{
STATUS_OK = 0, /* 正常返回 */
STATUS_DIV_BY_ZERO = 1, /* 被零除 */
STATUS_NUMBER_ERROR = 2, /* 操作数错误 */
STATUS_OPTERATOR_ERROR = 3, /* 运算符错误 */
STATUS_INVALID_TOKEN = 4, /* 非法字符 */
STATUS_STACK_OVERFLOW = 5, /* 堆栈溢出 */
} status_t;
/*
* 取得一元运算符，若opt_in_stack不为NULL，比较栈外新式，并
* 通过opt_in_stack返回栈外形式，否则，比较栈内形式。之所以
* 分为两个形式是为了在堆栈内部区别加减号和正负号。
*/
int is_unary_opt(char opt, char *opt_in_stack)
{
/* TODO: 在下面对应的两个数组中添加自己的一元操作符 */
static char *opt_list = "+-";
static char *opt_in_stack_list = "s!";
if (opt_in_stack != NULL)
{
char *loc = strchr(opt_list, opt);
if (loc == NULL)
return 0;
*opt_in_stack = opt_in_stack_list[loc - opt_list];
return 1;
}
return strchr(opt_in_stack_list, opt) != NULL;
}
/*
* 取得运算符优先级，如果不是运算符，则返回0，数字越大表示优
* 先级越低
*/
int get_bin_opt(char op)
{
/* TODO: 在这里添加你自己的二元操作符 */
switch (op)
{
case '*':
case '/':
return 1;
case '+':
case '-':
return 2;
}
return 0;
}
/* 根据堆栈栈顶的操作数及运算符计算。 */
status_t calc_opt_with_stack(const char *opt_stack, char **opt_stack_top,
const double *num_stack, double **num_stack_top)
{
if (*opt_stack_top - opt_stack < 0)
return STATUS_OPTERATOR_ERROR;
if (is_unary_opt(**opt_stack_top, NULL))
{
if (*num_stack_top - num_stack < 0)
return STATUS_NUMBER_ERROR;
/* TODO: 在这里添加你自己的一元运算符的计算方法 */
switch (**opt_stack_top)
{
case 's':
break;
case '!':
**num_stack_top = -**num_stack_top;
break;
default:
return STATUS_OPTERATOR_ERROR;
}
--*opt_stack_top;
return STATUS_OK;
}
if (*num_stack_top - num_stack < 1)
return STATUS_NUMBER_ERROR;
/* TODO: 在这里添加你的二元运算符的计算方法 */
switch (**opt_stack_top)
{
case '+':
(*num_stack_top)[-1] += **num_stack_top;
break;
case '-':
(*num_stack_top)[-1] -= **num_stack_top;
break;
case '*':
(*num_stack_top)[-1] *= **num_stack_top;
break;
case '/':
/* 被除数为0 */
if (**num_stack_top == 0)
return STATUS_DIV_BY_ZERO;
(*num_stack_top)[-1] /= **num_stack_top;
break;
default:
return STATUS_OPTERATOR_ERROR;
}
--*opt_stack_top;
--*num_stack_top;
return STATUS_OK;
}
/*
* 运算主程序，将改变pos的指向，可以据此判断错误位置，如果解
* 析成功，答案由ans返回。如果str_pos为空，安静地返回OK。
*/
status_t do_calculate(const char ** str_pos, double *ans)
{
/* 当前是否需要数字（比如操作符和括号后） */
int now_need_num = 1;
/* 操作数栈和符号栈 */
double num_stack[STACK_MAX], *num_stack_top = num_stack - 1;
char opt_stack[STACK_MAX], *opt_stack_top = opt_stack - 1;
if (str_pos == NULL)
return STATUS_OK;
while (**str_pos != '\0')
{
/* 如果为空白字符，直接忽略掉 */
if (isspace(**str_pos))
++*str_pos;
/* 如果为数字，直接入栈 */
else if (isdigit(**str_pos) || **str_pos == '.')
{
/* 将读出的数字的个数 */
int read_size;
/* 如果当前不期待操作数，返回错误 */
if (!now_need_num)
return STATUS_NUMBER_ERROR;
/* 读取浮点数字到栈顶 */
CHECK_STACK_OVERFLOW(num);
sscanf(*str_pos, "%lf%n", ++num_stack_top, &read_size);
*str_pos += read_size;
/* 计算位于当前数字之前的一元操作符 */
while (!IS_STACK_EMPTY(opt)
&& is_unary_opt(*opt_stack_top, NULL))
CALC_OPT_IN_STACK();
/* 不可连续出现两个数字 */
now_need_num = 0;
}
/* 如果为括号，直接进栈 */
else if (**str_pos == '(')
{
/* 这时应该是期待操作数的 */
if (!now_need_num)
return STATUS_OPTERATOR_ERROR;
/* 括号入栈 */
CHECK_STACK_OVERFLOW(opt);
*++opt_stack_top = *(*str_pos)++;
/* 括号后允许出现数字 */
now_need_num = 1;
}
/* 如果为反括号，需要判断括号是否匹配 */
else if (**str_pos == ')')
{
/* 这时应该不期待操作数 */
if (now_need_num)
return STATUS_OPTERATOR_ERROR;
/* 遇到反括号，持续出栈直到遇到相应括号 */
while (!IS_STACK_EMPTY(opt) && *opt_stack_top != '(')
CALC_OPT_IN_STACK();
/*
* 如果找不到相应括号，出错返回。否则，括号出栈
* ，即消掉了一对括号
*/
if (IS_STACK_EMPTY(opt))
return STATUS_OPTERATOR_ERROR;
/* 括号出栈 */
--opt_stack_top;
/* 计算位于当前括号之前的一元操作符 */
while (!IS_STACK_EMPTY(opt)
&& is_unary_opt(*opt_stack_top, NULL))
CALC_OPT_IN_STACK();
/* 迭代下一个字符 */
++*str_pos;
/* 反括号后不允许出现数字 */
now_need_num = 0;
}
/* 其他情况 */
else
{
char ch = **str_pos;
/* 如果为二元操作符 */
if (get_bin_opt(ch))
{
/*
* 如果不需要出现数字，并且操作符栈非空并且栈顶
* 元素不是括号，并且栈顶元素的优先级高于当前运
* 算符，就计算栈内的前一次运算。因为那次运
* 算优先级比当前运算高，所以必须先计算。
*/
if (!now_need_num
&& !IS_STACK_EMPTY(opt)
&& get_bin_opt(*opt_stack_top) != 0
&& get_bin_opt(*opt_stack_top) <= get_bin_opt(ch))
{
CALC_OPT_IN_STACK();
}
/* 如果需要数字，可以认为这时出现的是一元操作符 */
else if (now_need_num)
{
/*
* 如果为一元操作符，则替换ch为操作符的栈内
* 形式，否则，返回操作符错误。
*/
if (!is_unary_opt(ch, &ch))
return STATUS_OPTERATOR_ERROR;
}
/* 操作符入栈 */
CHECK_STACK_OVERFLOW(opt);
*++opt_stack_top = ch;
/* 操作符后期待操作数 */
now_need_num = 1;
}
/* 如果为一元操作符 */
else if (is_unary_opt(ch, &ch))
{
/* 一元操作符应该出现在需要操作数的位置。 */
if (!now_need_num)
return STATUS_OPTERATOR_ERROR;
/* 一元操作符入栈 */
CHECK_STACK_OVERFLOW(opt);
*++opt_stack_top = ch;
/* 一元操作符后期待数字 */
now_need_num = 1;
}
/* 其他情况，报符号错误 */
else
return STATUS_INVALID_TOKEN;
/* 移动位置指针 */
++*str_pos;
}
}
/* 计算剩余的操作符 */
while (!IS_STACK_EMPTY(opt))
CALC_OPT_IN_STACK();
/* 如果操作数栈内还存有除结果以外的数字，出错。 */
if (GET_STACK_SIZE(num) != 1)
return STATUS_NUMBER_ERROR;
/* 返回计算结果 */
if (ans != NULL)
*ans = *num_stack_top;
return STATUS_OK;
}
/* 接口函数，处理输入输出，方便计算函数使用 */
void calculate(const char* str)
{
double ans;
const char *cur_pos = str;
status_t ret = do_calculate(&cur_pos, &ans);
if (ret == STATUS_OK)
{
if (ans > 1e8 || IS_DOUBLE_ZERO(ans - (int)ans))
printf("结果：%.12g\n", ans);
else
printf("结果：%.12f\n", ans);
return;
}
/* 处理错误 */
else
{
int error_pos = cur_pos - str, expr_len = strlen(str);
const char *str_prefix, *str_postfix, *str_show;
if (expr_len > 40 && error_pos > 20)
{
str_prefix = "... ";
str_show = cur_pos - 20;
error_pos = 7 + 4 + 20;
}
else
{
str_prefix = "";
str_show = str;
error_pos += 7;
}
str_postfix = (expr_len - error_pos > 20 ? " ..." : "");
fprintf(stderr, "表达式解析错误！\n位置：%s%.40s%s\n%*c\n",
str_prefix, str_show, str_postfix, error_pos, '^');
}
fputs("错误：", stderr);
switch (ret)
{
case STATUS_OK:
break;
case STATUS_DIV_BY_ZERO:
fputs("被零除", stderr);
break;
case STATUS_NUMBER_ERROR:
fputs("操作数错误", stderr);
break;
case STATUS_OPTERATOR_ERROR:
fputs("运算符错误", stderr);
break;
case STATUS_INVALID_TOKEN:
fputs("非法字符", stderr);
break;
case STATUS_STACK_OVERFLOW:
fputs("栈溢出（表达式太过复杂？）", stderr);
break;
}
fputc('\n', stderr);
}
int main(void)
{
char str[1001];
puts("简易计算器 制作：StarWing\n输入end退出本程序。");
while (printf("> "), fgets(str, 1000, stdin) != NULL)
{
char *end = strchr(str, '\n');
if (end != NULL)
*end = '\0';
if (end != str)
{
if (!strcmp(str, "end"))
break;
calculate(str);
}
}
return 0;
}
/* cc_flags += -g */
2008-11-19 07:50
2008-11-19 12:28
2008-11-19 19:23
2008-11-19 22:28
