数据结构实验3——用栈求解算术表达式

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cwchar>
  4 #include <windows.h>
  5 
  6 using namespace std;
  7 #define ok 1
  8 #define error 0
  9 #define overflow -2
 10 #define maxn 100
 11 
 12 typedef struct{
 13     char *base;
 14     char *top;
 15     int stacksize;
 16 }SqStack;
 17 
 18 typedef struct SNode{
 19     int data;
 20     struct SNode *next;
 21 }SNode, *linkstack;
 22 
 23 char ch, theta, x;
 24 SqStack OPTR, OPND;
 25 char oper[7] = {‘(‘, ‘)‘, ‘+‘, ‘-‘, ‘*‘, ‘/‘,‘#‘};
 26 //栈的初始化
 27 int initStack(SqStack &s){
 28     s.base = new char[maxn];
 29     if(!s.base) exit(overflow);
 30     s.top = s.base;
 31     s.stacksize = maxn;
 32     return ok;
 33 }
 34 
 35 //入栈
 36 int push(SqStack &s, char e){
 37     if(s.base - s.top == s.stacksize) return error;
 38     *s.top ++ = e;
 39     return ok;
 40 }
 41 
 42 //出栈
 43 int pop(SqStack &s, char &e){
 44     if(s.base == s.top) return error;
 45     e = *--s.top;
 46     return ok;
 47 }
 48 
 49 char gettop(SqStack s){
 50     if(s.top != s.base)
 51         return *(s.top - 1);
 52 }
 53 
 54 //判断栈是否为空
 55 bool stackempty(SqStack &s){
 56     return s.top != s.base;
 57 }
 58 
 59 bool in(char ch){
 60     for(int i = 0; i < 7; i ++ )
 61         if(ch == oper[i]) return true;
 62     return false;
 63 }
 64 
 65 char precede(char theta1, char theta2){
 66     if((theta1 == ‘(‘ && theta2 == ‘)‘) || (theta1 == ‘#‘ && theta2 == ‘#‘))
 67         return ‘=‘;
 68     else if (theta1 == ‘(‘ || theta1 ==‘#‘ || theta2== ‘(‘ || ((theta1==‘+‘||theta1==‘-‘) && (theta2 == ‘*‘||theta2 ==‘/‘)))
 69         return ‘<‘;
 70     else return ‘>‘;
 71 }
 72 
 73 char operate(char first, char theta, char second){
 74     switch(theta){
 75         case ‘+‘: return (first - ‘0‘) + (second - ‘0‘) + 48;
 76         case ‘-‘: return (first - ‘0‘) - (second - ‘0‘) + 48;
 77         case ‘*‘: return (first - ‘0‘) * (second - ‘0‘) + 48;
 78         case ‘/‘: return (first - ‘0‘) / (second - ‘0‘) + 48;
 79     }
 80     return 0;
 81 }
 82 
 83 char evaluateExpression(){
 84     int j = initStack(OPND);
 85     j = initStack(OPTR);
 86     j = push(OPTR, ‘#‘);
 87     cin >> ch;
 88     while(ch != ‘#‘ || gettop(OPTR) != ‘#‘){
 89         char a, b;
 90         if(!in(ch)) {
 91             j = push(OPND, ch);
 92             cin >> ch;
 93         }
 94         else {
 95             switch (precede(gettop(OPTR), ch)) {
 96                 case ‘<‘: {
 97                     j = push(OPTR, ch);
 98                     cin >> ch;
 99                     break;
100                 }
101                 case ‘>‘: {
102                     j = pop(OPTR, theta);
103                     j = pop(OPND, b);
104                     j = pop(OPND, a);
105                     j = push(OPND, operate(a, theta, b));
106                     break;
107                 }
108                 case ‘=‘: {
109                     j = pop(OPTR, x);
110                     cin >> ch;
111                     break;
112                 }
113             }
114         }
115     }
116     return gettop(OPND);
117 }
118 
119 int main()
120 {
121     char res;
122     int c;
123     SetConsoleOutputCP(65001);
124     cout<<"-----------------"<<endl;
125     cout<<"0-9之内的多项式计算"<<endl;
126     cout<<"1.计算"<<endl;
127     cout<<"0.退出"<<endl;
128     cout<<"请选择：";
129     while(scanf("%d", &c) != EOF){
130         switch(c){
131             case 1:{
132                 cout<<"请输入要计算的表达式（操作数和结果都在0-9的范围内,以#结束）："<<endl;
133                 res = evaluateExpression();
134                 cout<<"计算结果为"<<res - 48<<endl<<endl;
135                 break;
136             }
137             case 0:{
138                 cout<<"退出成功\n"<<endl;
139                 exit(0);
140             }
141             default:
142                 break;
143         }
144     }
145 }