利用栈来完成表达式求值
一个表达式要求值,分为操作数部分和运算符部分,求值的过程便是运算符对操作数进行操作。
首先我们定义两个栈,一个栈存放运算符,先放个#进去,代表开始,然后记得结束最后一个字符也是#,这样代表结束。然后建立一个栈存放操作数。
算法:
定义一个字符来getchar字符,然后判断。首先判断这是字符是不是#或者现在运算符栈的top是不是#,如果两个都是#那么运算完成。
然后判断,不是运算符的话就存入操作数栈内
如果是运算符,那么判断,这个运算符与现在运算符栈top位置的运算符的关系,两者的优先性,根据优先性来进行下一步操作
比如top位置是‘-‘,然后字符是‘)’,那么在运算符栈内肯定有一个“(”与字符‘)’对应,如果没有,那么肯定输入有问题。因为有’(‘在栈内所以‘-’的优先性是大于‘)’的,获得字符‘>’所以进行运算,也就是减。首先从操作数里面取top出来,作为减数,然后top–,然后再取top作为被减数,因为存放顺序的关系,先进去的肯定是在前面。然后在字符“>”的情况下是不进行getchar的,因为也就进行了运算,所以现在字符还是‘)’,然后现在运算符栈内的就是‘(’,如果不是,那么继续运算,因为可能出现(7+2+2)这种,那么多算一次‘>’的情况就行。然后(与)判断结果是=,让运算符栈内(消掉,然后现在括号内的运算已经完毕,然后getchar获取下一个字符,继续进行判断!
代码可以直接运行
#include"consts.h"
typedef struct {
char S[100];
int top;
}CHARStack;
void InitStack(CHARStack *S) {
S->top = -1;
}
void Push(CHARStack* S, char ch) {
if (S->top >= 99) {
printf("栈满!\n");
exit(0);
}
else {
S->top++;
S->S[S->top] = ch;
}
}
char GetTop(CHARStack* S) {
if (S->top==-1) {
printf("栈空!\n");
exit(0);
}
else {
return S->S[S->top];
}
}
int TRIn(char ch) { //是运算符就返回1,不是运算符返回0
if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(' || ch == ')' || ch == '#') {
return 1;
}
else return 0;
}
char Precede(char ch1, char ch2) {
if (ch1 == '+') {
if (ch2 == '+')return '>';
if (ch2 == '-')return '>';
if (ch2 == '*')return '<';
if (ch2 == '/')return '<';
if (ch2 == '(')return '<';
if (ch2 == ')')return '>';
if (ch2 == '#')return '>';
}
else if (ch1 == '-') {
if (ch2 == '+')return '>';
if (ch2 == '-')return '>';
if (ch2 == '*')return '<';
if (ch2 == '/')return '<';
if (ch2 == '(')return '<';
if (ch2 == ')')return '>';
if (ch2 == '#')return '>';
}
else if (ch1 == '*') {
if (ch2 == '+')return '>';
if (ch2 == '-')return '>';
if (ch2 == '*')return '>';
if (ch2 == '/')return '>';
if (ch2 == '(')return '<';
if (ch2 == ')')return '>';
if (ch2 == '#')return '>';
}
else if (ch1 == '/') {
if (ch2 == '+')return '>';
if (ch2 == '-')return '>';
if (ch2 == '*')return '>';
if (ch2 == '/')return '>';
if (ch2 == '(')return '<';
if (ch2 == ')')return '>';
if (ch2 == '#')return '>';
}
else if (ch1 == '(') {
if (ch2 == '+')return '<';
if (ch2 == '-')return '<';
if (ch2 == '*')return '<';
if (ch2 == '/')return '<';
if (ch2 == '(')return '<';
if (ch2 == ')')return '=';
if (ch2 == '#') {
printf("输入的多项式有误!\n");
exit(0);
}
}
else if (ch1 == ')') {
if (ch2 == '+')return '>';
if (ch2 == '-')return '>';
if (ch2 == '*')return '>';
if (ch2 == '/')return '>';
if (ch2 == '(') {
printf("输入的多项式有误!\n");
exit(0);
}
if (ch2 == ')')return '>';
if (ch2 == '#')return '>';
}
else if (ch1 == '#') {
if (ch2 == '+')return '<';
if (ch2 == '-')return '<';
if (ch2 == '*')return '<';
if (ch2 == '/')return '<';
if (ch2 == '(')return '<';
if (ch2 == ')') {
printf("输入的多项式有误!\n");
exit(0);
}
if (ch2 == '#')return '=';
}
else {
printf("出错!");
exit(0);
return 0;
}
}
void Pop(CHARStack* S, char* ch) {
if (S->top == -1) {
printf("栈空!\n");
exit(0);
}
else {
*ch=S->S[S->top];
S->top--;
}
}
int changchartonumber(char ch) {
if (ch == '0') {
return 0;
}
else if (ch == '1') {
return 1;
}
else if (ch == '2') {
return 2;
}
else if (ch == '3') {
return 3;
}
else if (ch == '4') {
return 4;
}
else if (ch == '5') {
return 5;
}
else if (ch == '6') {
return 6;
}
else if (ch == '7') {
return 7;
}
else if (ch == '8') {
return 8;
}
else if (ch == '9') {
return 9;
}
else {
return (int)ch;
}
}
char Operate(char ch1, char theta, char ch2) {
int c1, c2;
c1 = changchartonumber(ch1);
c2 = changchartonumber(ch2);
if (theta == '+') {
return c1 + c2;
}
else if (theta == '-') {
return c1 - c2;
}
else if (theta == '*') {
return c1 * c2;
}
else if (theta == '/') {
return c1 / c2;
}
else {
printf("错误");
exit(0);
return '0';
}
}
int main() {
char c,theta,a,b,xl,p;
int x;
CHARStack *OPTR, *OPND; //定义OPTR为运算符栈,OPND为运算数栈
OPTR = (CHARStack*)malloc(sizeof(CHARStack));
OPND = (CHARStack*)malloc(sizeof(CHARStack));
InitStack(OPTR);
Push(OPTR,'#');
InitStack(OPND);
c = getchar();
while (c != '#' || GetTop(OPTR) != '#') {
if (!TRIn(c)) { //不是运算符
Push(OPND, c);
c = getchar();
}
else {
switch (Precede(GetTop(OPTR),c))
{
case'<'://栈顶元素优先权低
Push(OPTR, c); c = getchar(); break;
case'='://脱括号并接受下一个字符
Pop(OPTR, &p); c = getchar(); break;
case'>'://栈顶元素优先权高
Pop(OPTR, &theta);
Pop(OPND, &b);
Pop(OPND, &a);
Push(OPND, Operate(a, theta, b));
break;
}
}
}
printf("结果为:%d",(int)OPND->S[OPND->top]);
return 0;
}
头文件
#pragma once
#include<stdio.h> //EOF(=^Z或F6),NULL
#include<malloc.h> //malloc()等
#include<limits.h> //INT_MAX等
#include<string.h>
#include<stdlib.h> //atoi()
#include<io.h> //eof
#include<math.h> //floor(),ceil(),abs()*
#include<process.h> //exit()*
/*函数结果状态代码*/
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR -1
#define INFEASIBLE -1
这个过程当中其实需要两个类型栈来进行运算的,但是我图方便就按一个类型就是char类型进行运算,然后根据ASCII码与数字的关系,灵活转换,就可以达到两个类型栈的效果。比如字符‘5’-‘2’两个字符相减结果肯定是ASCII码,但由于位置的特殊性,结果还是3,但是这种算法是错误的。因为实际上是53-50=3;这个过程我利用一个changchartonumber函数,让他们变成int值直接的运算,要不然‘5’+‘2’实际上是53+50,结果是无法估计的!然后根据直接把结果存放在栈内。比如结果3,我直接把3存放在内,但是3代表的字符是未知的对于我来说,那么输出结果的时候,可以直接(int)强制转型,输出的便是3.其实char型的本质是int型,ASCII码表就是对于int与char之间的关系,多理解就可以了
本人在校大学生,菜鸟学习中,欢迎大佬指导,欢迎大家点赞关注!