整体过程是遍历一次输入的所需运算的字符串
每次对一个元素进行判断和操作，一共两个栈（一个数字栈，一个符号栈）
（1）如果是数字就入数字栈，然后继续操作下一个字符串中的元素
下面是对括号的一些操作：
如果是左括号，就进符号栈，然后继续操作下一个字符串中的元素
如果是右括号，就让符号栈栈顶元素出栈，让数字栈栈顶和次栈顶的两个元素出栈进行运算，并将运算结果入数字栈，一直循环此操作直至遇见符号栈栈顶为左括号为止，遇见左括号后将其出符号栈，并继续操作下一个字符串中的元素
（2）如果是符号：
如果符号栈为空，就直接入符号栈
如果符号栈栈顶的符号的优先级大于当前正在操作的字符串中的元素，就将符号栈栈顶符号出栈，将数字栈栈顶和次栈顶的两个元素出栈，进行运算后将结果入数字栈
如果符号栈栈顶的符号的优先级小于当前正在操作的字符串中的元素，就入符号栈
（3）当字符串中的元素全部遍历完后如果符号栈仍然有元素，就继续从符号栈栈顶出一个元素，从数字栈栈顶出两个元素，计算后将结果入数字栈，循环此操作直至符号栈为空为止
#include#include #include #define n 50 //数字栈 typedef struct nodeFirst{ double a[n]; int size;// 表示栈中含有的元素数量 } stackFirst; //符号栈 typedef struct nodeSecond{ char a[n]; int size; } stackSecond; //数字栈出栈 double pop(stackFirst *p) { if (p -> size == 0) //printf("空栈"); return 0; else { --(p -> size); return p -> a[p -> size]; } } //符号栈出栈 char popSecond(stackSecond *p) { if (p -> size == 0) return 0; else { --(p -> size); return p -> a[p -> size]; } } //返回数字栈栈顶元素 double top(stackFirst *p) { if (p -> size == 0) return 0;//输出0表示空 else { return p -> a[p -> size - 1]; } } //返回符号栈栈顶元素 char topSecond(stackSecond *p) { if (p -> size == 0) return 0;//输出0表示空 else { return p -> a[p -> size - 1]; } } //将数字栈置空 int empty(stackFirst *p) { return p -> size == 0; } //将符号栈置空 int emptySecond(stackSecond *p) { return p -> size == 0; } //数字栈入栈 void push(stackFirst *p, double b) { p -> a[p -> size] = b; ++p -> size; } //符号栈入栈 void pushSecond(stackSecond *p, char b) { p -> a[p -> size] = b; ++p -> size; } //比较符号优先级 int compare(char str) { if (str == '+' || str == '-') { return 1; } else if (str == '*' || str == '/') { return 2; } else { return 0; } } //计算 double counter(double x, double y, char str) { double ans = 0.0; if (str == '-') { ans = x - y; } else if (str == '+') { ans = x + y; } else if (str == '*') { ans = x * y; } else { ans = x / y; } return ans; } int main(void) { //数字栈 stackFirst *first; first = (stackFirst *) malloc(sizeof(stackFirst)); first -> size = 0; //符号栈 stackSecond *second; second = (stackSecond *) malloc(sizeof(stackSecond)); second -> size = 0; char a[100]; printf("请输入需要计算的算术表达式：n"); scanf("%s", a); int length = (int)strlen(a); //在用户所输入的式子后面加‘#’号 a[length] = '#'; length = length + 1; int i = 0; double x = 0; //出栈用于计算的符号 char strtest; //出栈用于计算的数字 double numFirst, numSecond; //用于保存当次计算结果 double res; while (a[i] != '#') { x = 0; //如果是数字就入数字栈 if (a[i] >= '0' && a[i] <= '9') { while (a[i] >= '0' && a[i] <= '9') { x *= 10; x += a[i++] - '0'; } //计算是小数的情况 if (a[i] == '.') { double d = 0.1; ++i; while (a[i] >= '0' && a[i] <= '9') { x += ((a[i] - '0') * d); d *= 0.1; ++i; } } //数字进栈 push(first, x); continue; } //如果是符号，且符号栈为空，符号直接进符号栈 if (second -> size == 0 && (a[i] == '+' || a[i] == '-' || a[i] == '*' || a[i] == '/' || a[i] == '(' || a[i] == ')')) { pushSecond(second, a[i]); ++i; continue; } //如果是左括号，直接入栈 if (a[i] == '(') { pushSecond(second, a[i]); ++i; continue; } //如果是右括号，循环取出符号栈中的符号，跟数字栈中两个数字参与运算后入数字栈，直到碰到左括号为止 if (a[i] == ')') { while (topSecond(second) != '(') { strtest = popSecond(second); numFirst = pop(first); numSecond = pop(first); res = counter(numSecond, numFirst, strtest); //计算结果入数据栈 push(first, res); } //左括号出栈 popSecond(second); ++i; continue; } //最后一种情况是要入符号栈 while (compare(a[i]) <= compare(topSecond(second))) { strtest = popSecond(second); numFirst = pop(first); numSecond = pop(first); res = counter(numSecond, numFirst, strtest); //计算结果入数据栈 push(first, res); } //入符号栈 pushSecond(second, a[i]); ++i; } //如果符号栈还不为空的情况 while (second -> size > 0) { strtest = popSecond(second); numFirst = pop(first); numSecond = pop(first); res = counter(numSecond, numFirst, strtest); //计算结果入数据栈 push(first, res); } //输出最终计算结果 printf("%lfn", top(first)); return 0; }
最终运行结果： 例如： 输入：4.2+5*(2.1+(1+2)) 输出：29.700000
