利用栈实现表达式的计算：
例如：12×(5+6×9)+7×8+(5-6×8+5/6)×12
要解决的问题主要有两个：
#include<bits/stdc++.h>
using namespace std;
stack<char>sml; //储存符号的符号栈
stack<double>dgt; //储存数字的数字栈
stack<double>tmp; //临时栈，作用为将多个数字字符转换成数字
static double ans = 0.0;
void mixed() //计算表达式的函数
{
double t = 0;
if(sml.top() == '-' || sml.top() == '+') //如果栈顶为‘-’或者为‘+’，则将栈顶元素加入ans中
{
if(sml.top() == '-')ans -= dgt.top();
else if(sml.top() == '+') ans += dgt.top();
dgt.pop(); //将已经计算完的出栈
sml.pop();
}
else if(sml.top() == '*' || sml.top() == '/') //将*或/的结果入栈
{
double temp = dgt.top();
dgt.pop();
if(sml.top() == '*') t = dgt.top() * temp;
else if(sml.top() == '/') t = dgt.top() / temp;
dgt.pop();
dgt.push(t);
sml.pop();
}
}
int getnum() //转化多位数的函数
{
int index = 0 , ans1 = 0;
while(!tmp.empty())
{
int num = tmp.top();
tmp.pop();
ans1 += num * pow(10 , index++);
}
return ans1;
}
void cut() //计算括号内表达式的值
{
while(sml.top() != '(')
mixed();
sml.pop();
}
void getvalue(char *exp , int len)
{
for(int i = 0 ; i < len ; i++)
{
if(isdigit(exp[i]))
{
double num = exp[i] - '0';
tmp.push(num);
}
else
{
if(!tmp.empty())
{
double num = getnum();
dgt.push(num);
}
if(exp[i] == '(')
sml.push(exp[i]);
else if(exp[i] == ')')
{
cut();
ans += dgt.top();
dgt.pop();
dgt.push(ans);
ans = 0;
}
else
sml.push(exp[i]);
}
}
if(!tmp.empty())
{
double num = getnum();
dgt.push(num);
}
while(!sml.empty())
mixed();
cout<<dgt.top() + ans; //自己模拟运算一下有助于理解
}
int main()
{
char exp[100];
cin>>exp;
int len = strlen(exp);
getvalue(exp , len);
return 0;
}运行结果：
二：将中缀表达式转化为后缀表达式（这里进行了升级，可以实现"^" 和 "%"的运算，并且可以读取小数点）
下面是代码：
#include<bits/stdc++.h>
using namespace std;
stack<char>tmp; //储存后缀表达式的栈
stack<char>sml; //储存符号的栈
stack<double>dgt; //储存数的栈
stack<char>temp; //转化栈， 将字符串转化为数值
double num[1000];
int cnt = 0;
bool flag = false; //判断数中是否有小数点的标志
void getnum(bool &flag); //将字符串转化为数值的函数
void change(char *exp); //将中缀表达式转化为后缀表达式的函数
void getvalue(); //计算后缀表达式的函数
int getprior(char ch); //获取符号优先级的函数；
void cal(double num1 , double num2 , char op); //计算函数
int main()
{
char exp[100];
cin>>exp;
change(exp);
getvalue();
return 0; //12.2*(15.4+5*2^3)*12.3+4+5%6+10*12.2
}
int getprior(char ch)
{
if(ch == '-' || ch == '+')
return 2;
else if(ch == '*' || ch == '/' || ch == '%')
return 3;
else if(ch == '^')
return 4;
else if(ch == '(')
return 5;
else if(ch == ')')
return 1;
}
void getnum(bool &flag)
{
double ans = 0;
double t = 0;
int counted = 0; //计算小数点后有几位
int index = 0; //整数部分的下标
while(!temp.empty())
{
if(flag) //如果有小数点
{
while(temp.top() != '.')
{
int i = temp.top() - '0';
t = t + i * pow(10 , counted);
counted++;
temp.pop();
}
temp.pop(); //将小数点出栈
t = t * pow(10 , -counted);
flag = false; //小数点已出栈
}
int i = temp.top() - '0';
ans = ans + i * pow(10 , index);
index++;
temp.pop();
}
ans += t; //将小数部分和整数部分相加
num[cnt] = ans;
}
void change(char *exp)
{
int len = strlen(exp);
for(int i = 0 ; i < len ; i++)
{
if(isdigit(exp[i]) || exp[i] == '.')
{
if(exp[i] == '.')
flag = true;
temp.push(exp[i]);
}
else
{
if(!temp.empty())
{
cnt++;
getnum(flag);
char t = '1'; //标记是数字
tmp.push(t);
}
if(sml.empty() || exp[i] == '(')
sml.push(exp[i]);
else
{
if(exp[i] == ')')
{
while(sml.top() != '(')
{
char ch = sml.top();
tmp.push(ch);
sml.pop();
}
sml.pop(); //将'('出栈
}
else
{
char ch = sml.top();
while(getprior(ch) >= getprior(exp[i]) && ch != '(') //如果栈顶符号的优先级大于这个符号，则压入后缀栈，等于因为在前面也压入后缀栈
{
tmp.push(ch);
sml.pop();
if(!sml.empty()) ch = sml.top();
else break;
}
sml.push(exp[i]);
}
}
}
}
if(!temp.empty())
{
cnt++;
getnum(flag);
char t = '1';
tmp.push(t);
}
while(!sml.empty())
{
char c = sml.top();
tmp.push(c);
sml.pop();
}
}
void getvalue()
{
stack<char>s;
while(!tmp.empty())
{
char c = tmp.top();
s.push(c);
tmp.pop();
}
int index = 1;
while(!s.empty())
{
char c = s.top();
if(isdigit(c))
{
dgt.push(num[index]);
index++;
s.pop();
}
else
{
double num2 = dgt.top();
dgt.pop();
double num1 = dgt.top(); //取出数值栈中的值
dgt.pop();
cal(num1 , num2 , c);
s.pop(); //将符号出栈
}
}
cout<<dgt.top();
}
void cal(double num1 , double num2 , char op)
{
switch (op)
{
case '+' : dgt.push(num1 + num2);break;
case '-' : dgt.push(num1 - num2);break;
case '*' : dgt.push(num1 * num2);break;
case '/' : dgt.push(num1 / num2);break;
case '%' : dgt.push( (int)num1 % (int)num2);break;
case '^' : dgt.push(pow((int)num1 , (int)num2));break;
}
} 运行结果：
下面更新一个我自己手写的栈(数据结构老师要求我们不嫩用STL中的数据结构，不然鬼想写 这鬼东西QAQ）
文件名：“stack.h”
代码块：
#ifndef STACK_H_INCLUDED
#define STACK_H_INCLUDED
#include<iostream>
using namespace std;
template<class Type>
class mystack
{
struct node
{
Type data;
node* next;
};
public:
mystack() //无参构造函数
{
top -> next = NULL;
top -> data = 0;
}
bool empty() //判断栈是否为空
{
return top -> next == NULL;
}
int getsize() //获取栈的大小的函数
{
node* p = top;
int counted = 0;
while(p -> next != NULL)
{
counted++;
p = p -> next;
}
return counted;
}
void push(Type elem) //将元素压入栈中的函数
{
node *q = new node;
q -> data = elem;
q -> next = top -> next;
top -> next = q;
}
void pop() //将栈顶元素出栈的操作
{
node* q = top -> next;
top -> next = top -> next -> next;
delete q;
}
Type gettop() //获取栈顶元素的函数
{
return top -> next -> data;
}
private:
node* top = new node;
};
#endif // STACK_H_INCLUDED下面是修改后的cpp文件（就是用上我自己手写的破栈的文件）
#include<iostream> //我自己调试了一下应该没什么问题
#include<cmath>
#include<cstring>
#include"stack.h"
using namespace std;
mystack<char>tmp; //储存后缀表达式的栈
mystack<char>sml; //储存符号的栈
mystack<double>dgt; //储存数的栈
mystack<char>temp; //转化栈， 将字符串转化为数值
double num[1000];
int cnt = 0;
bool flag = false; //判断数中是否有小数点的标志
void getnum(bool &flag); //将字符串转化为数值的函数
void change(char *exp); //将中缀表达式转化为后缀表达式的函数
void getvalue(); //计算后缀表达式的函数
int getprior(char ch); //获取符号优先级的函数；
void cal(double num1 , double num2 , char op); //计算函数
int main()
{
char exp[100];
cin>>exp;
change(exp);
getvalue();
return 0; //12.2*(15.4+5*2^3)*12.3+4+5%6+10*12.2
}
int getprior(char ch)
{
if(ch == '-' || ch == '+')
return 2;
else if(ch == '*' || ch == '/' || ch == '%')
return 3;
else if(ch == '^')
return 4;
else if(ch == '(')
return 5;
else if(ch == ')')
return 1;
}
void getnum(bool &flag)
{
double ans = 0;
double t = 0;
int counted = 0; //计算小数点后有几位
int index = 0; //整数部分的下标
while(!temp.empty())
{
if(flag) //如果有小数点
{
while(temp.gettop() != '.')
{
int i = temp.gettop() - '0';
t = t + i * pow(10 , counted);
counted++;
temp.pop();
}
temp.pop(); //将小数点出栈
t = t * pow(10 , -counted);
flag = false; //小数点已出栈
}
int i = temp.gettop() - '0';
ans = ans + i * pow(10 , index);
index++;
temp.pop();
}
ans += t; //将小数部分和整数部分相加
num[cnt] = ans;
}
void change(char *exp)
{
int len = strlen(exp);
for(int i = 0 ; i < len ; i++)
{
if(isdigit(exp[i]) || exp[i] == '.')
{
if(exp[i] == '.')
flag = true;
temp.push(exp[i]);
}
else
{
if(!temp.empty())
{
cnt++;
getnum(flag);
char t = '1';
tmp.push(t);
}
if(sml.empty() || exp[i] == '(')
sml.push(exp[i]);
else
{
if(exp[i] == ')')
{
while(sml.gettop() != '(')
{
char ch = sml.gettop();
tmp.push(ch);
sml.pop();
}
sml.pop(); //将'('出栈
}
else
{
char ch = sml.gettop();
if(getprior(ch) >= getprior(exp[i]) && ch != '(') //如果栈顶符号的优先级大于这个符号，则压入后缀栈
{
tmp.push(ch);
sml.pop();
}
sml.push(exp[i]);
}
}
}
}
if(!temp.empty())
{
cnt++;
getnum(flag);
char t = '1';
tmp.push(t);
}
while(!sml.empty())
{
char c = sml.gettop();
tmp.push(c);
sml.pop();
}
}
void getvalue()
{
mystack<char>s;
while(!tmp.empty())
{
char c = tmp.gettop();
s.push(c);
tmp.pop();
}
int index = 1;
while(!s.empty())
{
char c = s.gettop();
if(isdigit(c))
{
dgt.push(num[index]);
index++;
s.pop();
}
else
{
double num2 = dgt.gettop();
dgt.pop();
double num1 = dgt.gettop(); //取出数值栈中的值
dgt.pop();
cal(num1 , num2 , c);
s.pop(); //将符号出栈
}
}
cout<<dgt.gettop();
}
void cal(double num1 , double num2 , char op)
{
switch (op)
{
case '+' : dgt.push(num1 + num2);break;
case '-' : dgt.push(num1 - num2);break;
case '*' : dgt.push(num1 * num2);break;
case '/' : dgt.push(num1 / num2);break;
case '%' : dgt.push( (int)num1 % (int)num2);break;
case '^' : dgt.push(pow((int)num1 , (int)num2));break;
}
}