本代码没有处理某个数字为负数的情况,感兴趣的小伙伴可以分享自己的思路和代码
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>#define MAX_SIZE 100int numStk[MAX_SIZE], num_hh = 0;
char opStk[MAX_SIZE], op_hh = 0;// (1)Stack creation and initialization
/* -------------------------------- 数栈和符号栈begin -------------------------------- *//*** Push a number onto the number stack* @param num The number to push*/
void pushNum(int num) {numStk[++num_hh] = num;
}/*** Pop a number from the number stack* @return The popped number*/
int popNum() {return numStk[num_hh--];
}
/*** @return The top element of the number stack*/
int topNum() {return numStk[num_hh];
}/*** Push an operator onto the operator stack* @param op The operator to push*/
void pushOp(char op) {opStk[++op_hh] = op;
}/*** Pop an operator from the operator stack* @return The popped operator*/
char popOp() {return opStk[op_hh--];
}
/*** @return the number of operator stacks*/
int opStkSize()
{return op_hh;
}/* -------------------------------- 数栈和符号栈end -------------------------------- */// (2)Operator priority and calculation
/* -------------------------------- 计算器和优先级比较begin -------------------------------- */
int calc(int a, int b, char op)
{switch (op){case '+':return a + b;case '-':return a - b;case '*':return a * b;case '/':if (b == 0){perror("The divisor cannot be 0");exit(1);}return a / b;default:printf("c = %c",op);perror("Invalid operator");exit(1);}
}int precedence(char op)
{if (op == '+' || op == '-') return 1;if (op == '*' || op == '/') return 2;return 0;
}// 把符号栈全部取出和数栈进行计算
void calcSameLevel()
{while (opStkSize()){// 出栈计算int b = popNum();int a = popNum();char op = popOp();// 把运算结果入栈int tmp = calc(a,b,op);pushNum(tmp);}
}
/* -------------------------------- 计算器和优先级比较end -------------------------------- *///(3)Function for calculating expressions
/* -------------------------------- 控制数据提取和计算时机begin -------------------------------- */
/** 出栈和入栈的判定* 前一个符号 < 新增符号 入栈* 前一个符号 >= 新增符号 取出栈顶计算*/
int infixToPostfixEval(char *exp)
{// 处理多位数int num = 0;int pre = 0;// 0表示上一个是符号 1表示上一个是数字char preOP = ' ';// 保留前一个符号for (int i = 0; exp[i]; ++i){char c = exp[i];// 处理数字if (isdigit(c)){// 多位数if(pre){int tmp = num * 10 + (c-'0');// 更新栈顶popNum();//出栈pushNum(tmp);//入栈num = topNum();}// 新增else{int tmp = c - '0';pushNum(tmp);num = topNum();}pre = 1;}else if(c == '('){// 入符号栈opStk[++op_hh] = c;pre = 0;// 更新preOPpreOP = c;}else if(c == ')'){// 遇到右括号,则计算栈内直到左括号的所有运算符while (op_hh && opStk[op_hh] != '('){int b = numStk[num_hh--];int a = numStk[num_hh--];char op = opStk[op_hh--];numStk[++num_hh] = calc(a, b, op);}// 弹出左括号(不参与计算)if (op_hh) op_hh--;// 更新preOPpreOP = c;pre = 0; // 重置状态num = 0; // 重置数字}else{// 比较运算符优先级if(precedence(preOP) < precedence(c)){// 入栈opStk[++op_hh] = c;}else{//例: 2*2/4+3 preOP = '/' c = '+'calcSameLevel();// 新符号入栈opStk[++op_hh] = c;}// 更新pre状态pre = 0;// 更新preOPpreOP = c;// 更新numnum = 0;}}calcSameLevel();return popNum();
}/* -------------------------------- 控制数据提取和计算时机end -------------------------------- */
int main()
{// test :(2*3)+(100+(41*2))*((3*3)-(8/2))char expression[MAX_SIZE];printf("请输入一组正整数构成的表达式:\n");scanf("%s", expression);int res = infixToPostfixEval(expression);printf("%s = %d",expression,res);return 0;
}