头文件:
- #pragma once
- #include <iostream>
- #include <assert.h>
- #include <string>
- using namespace std;
- template<class Type>
- class SeqStack
- {
- public:
- SeqStack(size_t sz = INIT_SZ);
- ~SeqStack();
- public:
- bool empty()const;
- bool full()const;
- void show()const;
- bool push(const Type &x);
- bool pop();
- void gettop(Type &x);
- int length()const;
- void clear();
- void destory();
- void quit_system(Type &x);
- private:
- enum{ INIT_SZ = 64 };
- Type *base;
- int capacity;
- int top;
- };
- template<class Type>
- SeqStack<Type>::SeqStack(size_t sz = INIT_SZ)
- {
- capacity = sz > INIT_SZ ? sz : INIT_SZ;
- base = new Type[capacity];
- assert(base != NULL);
- top = 0;
- }
- template<class Type>
- SeqStack<Type>::~SeqStack()
- {
- destory();
- }
- // 判断栈是否满了
- template<class Type>
- bool SeqStack<Type>::full()const
- {
- return (top >= capacity);
- }
- // 判断是否为空栈
- template<class Type>
- bool SeqStack<Type>::empty()const
- {
- return (top == 0);
- }
- // 显示
- template<class Type>
- void SeqStack<Type>::show()const
- {
- if (top == 0)
- {
- cout << "the stack is empty!" << endl;
- return;
- }
- for (int i = top - 1; i >= 0; --i)
- {
- cout << base[i] << endl;
- }
- }
- // 入栈
- template<class Type>
- bool SeqStack<Type>::push(const Type &x)
- {
- if (full())
- {
- cout << "the stack is full,can not enter!" << endl;
- return false;
- }
- else
- {
- base[top] = x;
- top++;
- return true;
- }
- }
- // 出栈
- template<class Type>
- bool SeqStack<Type>::pop()
- {
- if (empty())
- {
- cout << "the stack is empty,can not pop!" << endl;
- return false;
- }
- else
- {
- top--;
- return true;
- }
- }
- // 获得栈顶元素
- template<class Type>
- void SeqStack<Type>::gettop(Type &x)
- {
- x = base[top - 1];
- }
- // 求栈长度
- template<class Type>
- int SeqStack<Type>::length()const
- {
- return top;
- }
- // 清空栈
- template<class Type>
- void SeqStack<Type>::clear()
- {
- top = 0;
- }
- // 摧毁栈
- template<class Type>
- void SeqStack<Type>::destory()
- {
- delete[]base;
- base = NULL;
- capacity = top = 0;
- }
- // 退出系统
- template<class Type>
- void SeqStack<Type>::quit_system(Type &x)
- {
- x = 0;
- }
主函数:
- #include "exp.h"
- #include "exp.h"
- //检查符号之间的优先级,1表示>,0表示=,-1表示<,c1栈内的运算,c2栈外的运算
- int check(char c1,char c2)
- {
- int a1,a2;
- if (c1 == '+' || c1 == '-')
- a1 = 3;
- if (c1 == '*' || c1 == '/')
- a1 = 5;
- if (c1 == '(')
- a1 = 1;
- if (c1 == ')')
- a1 = 7;
- if (c1 == '#')
- a1 = 0;
- if (c2 == '+' || c2 == '-')
- a2 = 2;
- if (c2 == '*' || c2 == '/')
- a2 = 4;
- if (c2 == '(')
- a2 = 6;
- if (c2 == ')')
- a1 = 1;
- if (c2 == '#')
- a2 = 0;
- if (a1 > a2)
- return 1;
- if (a1 == a2)
- return 0;
- if (a1 < a2)
- return -1;
- }
- //符号运算函数
- double sum(char c,double d1,double d2)
- {
- switch (c)
- {
- case '+':
- return d1 + d2;
- break;
- case '-':
- return d1 - d2;
- break;
- case '*':
- return d1 * d2;
- break;
- case '/':
- return d1 / d2;
- break;
- default:
- break;
- }
- }
- int main()
- {
- char *op = "+-*/()#";
- string str;
- cin >> str;
- //给表达式字符串str添加‘#’结束标志符
- str.append(1,'#');
- SeqStack<char> OPTR;//运算符栈
- SeqStack<double> OPND;//操作数栈
- int a = -1;
- //先将'#'入栈
- OPTR.push('#');
- while (true)
- {
- int b = a + 1;
- a = str.find_first_of(op,a + 1);
- if (a == string::npos)
- break;
- if (a != b)
- {
- string ss(str,b,a - b);
- double d = atof(ss.c_str());
- //数据先入栈
- OPND.push(d);
- }
- //运算符优先级比较
- char val;
- OPTR.gettop(val);
- int che = check(val,str[a]);
- if (-1 == che)//栈外优先级大直接入栈
- {
- OPTR.push(str[a]);
- }
- if (0 == che)//栈内外优先级相等则出栈
- {
- OPTR.pop();
- }
- if (1 == che)//栈内优先级大,出栈进行运算
- {
- char val;
- OPTR.gettop(val);
- double d1;
- OPND.gettop(d1);
- OPND.pop();
- double d2;
- OPND.gettop(d2);
- OPND.pop();
- d1 = sum(val,d2,d1);
- //运算结果入栈
- OPND.push(d1);
- OPTR.pop();
- a--;
- }
- }
- double s;
- OPND.gettop(s);
- cout << s << endl;
- return 0;
- }